exact.bib
@comment{{This file has been generated by bib2bib 1.97}}
@comment{{Command line: /usr/bin/bib2bib --expand -ob exact.bib -oc exact-list.bib ../all-entries.bib ./bib-gualandi.bib -c 'keywords : "graph coloring problem"' -c 'keywords : "exact methods"'}}
@inproceedings{Gelder02,
title = {Another Look at Graph Coloring via Propositional Satisfiability},
author = {A. Van Gelder},
pages = {48--54},
crossref = {symposium02},
keywords = {graph coloring problem, exact methods}
}
@inproceedings{GomShm02,
title = {Completing Quasigroups or Latin Squares: A Structured Graph Coloring Problem},
author = {C. Gomes and D. Shmoys},
pages = {22--39},
crossref = {symposium02},
keywords = {graph coloring problem, exact methods, applications, instances}
}
@incollection{Sew96,
title = {An Improved Algorithm for Exact Graph Coloring},
author = {E.C. Sewell},
pages = {359--373},
crossref = {dimacs96},
keywords = {graph coloring problem, exact methods}
}
@inproceedings{BarBri02,
title = {Graph Coloring for Air Traffic Flow Management},
author = {N. Barnier and P. Brisset},
booktitle = {CPAIOR'02: Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems},
year = {2002},
address = {Le Croisic, France},
month = {March},
pages = {133-147},
keywords = {graph coloring problem, exact methods, applications},
opturl = {citeseer.nj.nec.com/502256.html}
}
@article{Bre79,
title = {New Methods to Color the Vertices of a Graph},
author = {D.~Br{\'e}laz},
journal = {Communications of the ACM},
year = {1979},
number = {4},
pages = {251--256},
volume = {22},
keywords = {graph coloring problem, exact methods}
}
@article{Brown1972,
title = {Chromatic Scheduling and the Chromatic Number Problem},
author = {Brown, J. Randall},
journal = {Management Science},
year = {1972},
number = {4},
pages = {456--463},
volume = {19},
abstract = {The chromatic scheduling problem may be defined as any problem in which the solution is a partition of a set of objects. Since the partitions may not be distinct, redundant solutions can be generated when partial enumeration techniques are applied to chromatic scheduling problems. The necessary theory is developed to prevent redundant solutions in the application of partial enumeration techniques to chromatic scheduling problems with indistinguishable partitions and distinct objects. The chromatic number problem, which is the problem of finding the chromatic number of any graph, is a particular case of the chromatic scheduling problem. Two algorithms, basic and look-ahead, are developed for the chromatic number problem. Computational experience is given for each algorithm.},
copyright = {Copyright © 1972 INFORMS},
issn = {00251909},
jstor_articletype = {primary_article},
jstor_formatteddate = {Dec., 1972},
jstor_issuetitle = {Application Series, Part 1},
keywords = {graph coloring problem, exact methods},
publisher = {INFORMS},
url = {http://www.jstor.org/stable/2629029}
}
@techreport{Marecek2007TR,
title = {On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling},
author = {Edmund K. Burke and Jakub Mare{\v c}ek and Andrew J. Parkes and Hana Rudov{\' a}},
institution = {The University of Nottingham},
year = {2007},
address = {Nottingham},
number = {NOTTCS-TR-2007-10},
keywords = {graph coloring problem, exact methods, applications},
url = {http://arxiv.org/abs/0710.3603}
}
@article{CarDOl02,
title = {Bounding vertex coloring by truncated {\it multistage} branch and bound},
author = {Massimiliano Caramia and Paolo Dell'Olmo},
journal = {Networks},
year = {2004},
number = {4},
pages = {231-242},
volume = {44},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1002/net.20035},
keywords = {graph coloring problem, exact methods}
}
@article{CarDel01,
title = {Solving the minimum-weighted coloring problem},
author = {Massimiliano Caramia and Paolo Dell'Olmo},
journal = {Networks},
year = {2001},
number = {2},
pages = {88--101},
volume = {38},
keywords = {graph coloring problem, exact methods}
}
@article{Corneil1973a,
title = {An Algorithm for Determining the Chromatic Number of a Graph},
author = {D. G. Corneil and B. Graham},
journal = {SIAM Journal on Computing},
year = {1973},
number = {4},
pages = {311--318},
volume = {2},
abstract = {A heuristic algorithm for the determination of the chromatic number of a finite graph is presented. This algorithm is based on Zykov's theorem for chromatic polynomials, and extensive empirical tests show that it is the best algorithm available. Christofides' algorithm for the determination of chromatic number is described and is used in the comparison tests.},
keywords = {graph coloring problem, exact methods},
owner = {marco},
timestamp = {2013.08.07}
}
@article{DBLP:journals/dam/DesrosiersGH08,
title = {Efficient algorithms for finding critical subgraphs},
author = {Christian Desrosiers and Philippe Galinier and Alain Hertz},
journal = {Discrete Applied Mathematics},
year = {2008},
number = {2},
pages = {244-266},
volume = {156},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1016/j.dam.2006.07.019},
keywords = {graph coloring problem, exact methods}
}
@article{Epp03,
title = {Small Maximal Independent Sets and Faster Exact Graph Coloring},
author = {David Eppstein},
journal = {Journal of Graph Algorithms and Applications},
year = {2003},
number = {2},
pages = {131-140},
volume = {7},
bibsource = {DBLP, http://dblp.uni-trier.de},
ee = {http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf},
keywords = {graph coloring problem, exact methods}
}
@phdthesis{Gua08,
title = {Enhancing Constraint Programming-based Column Generation for Integer Programs},
author = {Stefano Gualandi},
school = {Dipartimento di Elettronica e Informazione, Politecnico di Milano},
year = {2008},
keywords = {graph coloring problem, exact methods}
}
@article{Gualandi2010,
title = {Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation},
author = {Stefano Gualandi and Federico Malucelli},
journal = {INFORMS Journal on Computing},
year = {2012},
number = {1},
pages = {81--100},
volume = {24},
doi = {10.1287/ijoc.1100.0436},
keywords = {graph coloring problem, exact methods},
optnote = {Also available in Optimization Online},
opturl = {http://www.optimization-online.org/DB_HTML/2010/03/2568.html},
owner = {marco},
timestamp = {2010.02.21}
}
@article{Hansen2009,
title = {Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results},
author = {Pierre Hansen and Martine Labb\'e and David Schindl},
journal = {Discrete Optimization},
year = {2009},
note = {Also as Tec.\ Rep.\ G-2005-76 Cahier du GERAD, Montreal},
number = {2},
pages = {135 - 147},
volume = {6},
abstract = {We consider two (0, 1)-linear programming formulations of the graph (vertex-) coloring problem, in which variables are associated with stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in which constraints express that two stable sets cannot have a common vertex, and large stable sets are preferred in the objective function. We identify facets with small coefficients for the polytopes associated with both formulations. We show by computational experiments that both formulations are about equally efficient when used in a branch-and-price algorithm. Next we propose some preprocessing, and show that it can substantially speed up the algorithm, if it is applied at each node of the enumeration tree. Finally we describe a cutting plane procedure for the set covering formulation, which often reduces the size of the enumeration tree.},
doi = {10.1016/j.disopt.2008.10.004},
keywords = {graph coloring problem, exact methods},
url = {http://www.optimization-online.org/DB_HTML/2005/12/1257.html}
}
@article{Held2012,
title = {Maximum-weight stable sets and safe lower bounds for graph coloring},
author = {Held, Stephan and Cook, William and Sewell, EdwardC.},
journal = {Mathematical Programming Computation},
year = {2012},
number = {4},
pages = {363-381},
volume = {4},
doi = {10.1007/s12532-012-0042-3},
issn = {1867-2949},
keywords = {Graph coloring; graph coloring problem; exact methods; Fractional chromatic number; Column generation; Maximum-weight stable set; Safe computations; 90-04; 90-08; 90C27; 90C35},
language = {English},
publisher = {Springer-Verlag},
url = {http://dx.doi.org/10.1007/s12532-012-0042-3}
}
@article{held2011safe,
title = {Safe lower bounds for graph coloring},
author = {Held, S. and Cook, W. and Sewell, E.},
journal = {Integer Programming and Combinatoral Optimization},
year = {2011},
pages = {261--273},
keywords = {graph coloring problem, lower bounds, exact methods},
publisher = {Springer}
}
@article{HerHer02,
title = {Finding the chromatic number by means of critical graphs},
author = {Francine Herrmann and Alain Hertz},
journal = {Journal of Experimental Algorithmics},
year = {2002},
pages = {10},
volume = {7},
doi = {http://doi.acm.org/10.1145/944618.944628},
issn = {1084-6654},
keywords = {graph coloring problem, exact methods},
publisher = {ACM Press, New York, NY, USA}
}
@article{KobJac85,
title = {A generalized implicit enumeration algorithm for graph coloring},
author = {Marek Kubale and Boguslaw Jackowski},
journal = {Communications of the ACM},
year = {1985},
number = {4},
pages = {412--418},
volume = {28},
address = {New York, NY, USA},
doi = {http://doi.acm.org/10.1145/3341.3350},
issn = {0001-0782},
keywords = {graph coloring problem, exact methods},
publisher = {ACM Press}
}
@article{LucMenMou06,
title = {An exact method for graph coloring},
author = {C. Lucet and F. Mendes and A. Moukrim},
journal = {Computers \& Operations Research},
year = {2006},
number = {8},
pages = {2189--2207},
volume = {33},
doi = {doi:10.1016/j.cor.2005.01.008},
keywords = {graph coloring problem, exact methods}
}
@article{MenZab06,
title = {A Branch-and-Cut algorithm for graph coloring},
author = {Isabel M{\'e}ndez-D{\'i}az and Paula Zabala},
journal = {Discrete Applied Mathematics},
year = {2006},
number = {5},
pages = {826--847},
volume = {154},
doi = {doi:10.1016/j.dam.2005.05.022},
keywords = {graph coloring problem, exact methods}
}
@incollection{MenZab01,
title = {A polyhedral approach for graph coloring},
author = {Isabel M{\'e}ndez-D{\'i}az and Paula Zabala},
booktitle = {Electronics Notes in Discrete Mathematics},
publisher = {springer},
year = {2001},
volume = {7},
keywords = {graph coloring problem, exact methods}
}
@article{DBLP:journals/dam/Mendez-DiazZ08,
title = {A cutting plane algorithm for graph coloring},
author = {Isabel M{\'e}ndez-D\'{\i}az and Paula Zabala},
journal = {Discrete Applied Mathematics},
year = {2008},
number = {2},
pages = {159-179},
volume = {156},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1016/j.dam.2006.07.010},
keywords = {graph coloring problem, exact methods}
}
@article{Malaguti2010,
title = {An Exact Approach for the Vertex Coloring Problem},
author = {Enrico Malaguti and Michele Monaci and Paolo Toth},
journal = {Discrete Optimization},
year = {2011},
number = {2},
pages = {174--190},
volume = {8},
keywords = {graph coloring problem, exact methods},
owner = {marco},
publisher = {Elsevier},
timestamp = {2010.08.06}
}
@misc{Marecek,
author = {Jakub Marecek},
keywords = {graph coloring problem, exact methods, links},
owner = {marco},
timestamp = {2009.03.10},
url = {http://www.cs.nott.ac.uk/~jxm/colouring/}
}
@article{MehTri96,
title = {A Column Generation Approach for Graph Coloring},
author = {A. Mehrotra and M. Trick},
journal = {INFORMS Journal On Computing},
year = {1996},
number = {4},
pages = {344--354},
volume = {8},
keywords = {graph coloring problem, exact methods, instances}
}
@article{Pee83,
title = {A correction to {B}relaz's modification of {B}rown's coloring algorithm},
author = {J. Peem\"oller},
journal = {Communications of the ACM archive},
year = {1983},
month = {August},
number = {8},
pages = {595--597},
volume = {26},
keywords = {graph coloring problem, exact methods}
}
@misc{Sch03,
title = {Graph coloring and linear programming},
author = {David Schindl},
month = {July},
note = {Presentation at First Joint Operations Research Days, Ecole Polytechnique F\'ed\'erale de Lausanne (EPFL), available on line (last visited June 2005)},
year = {2003},
keywords = {graph coloring problem, exact methods},
url = {http://roso.epfl.ch/ibm/jord03.html}
}
@article{Vas04,
title = {New Results on the Queens$\_n^2$ Graph Coloring Problem},
author = {Michel Vasquez},
journal = {Journal of Heuristics},
year = {2004},
number = {4},
pages = {407--413},
volume = {10},
doi = {10.1023/B:HEUR.0000034713.28244.e1},
issn = {1381-1231},
keywords = {graph coloring problem, exact methods},
publisher = {Kluwer Academic Publishers}
}
@proceedings{symposium02,
title = {Proceedings of the Computational Symposium on Graph Coloring and its Generalizations},
year = {2002},
address = {Ithaca, New York, USA},
editor = {D. S. Johnson and A. Mehrotra and M. Trick},
booktitle = {Proceedings of the Computational Symposium on Graph Coloring and its Generalizations}
}
@book{dimacs96,
title = {Cliques, Coloring, and Satisfiability: Second {DIMACS} Implementation Challenge, 1993},
editor = {David S. Johnson and Michael Trick},
publisher = {American Mathematical Society, Providence, RI, USA},
year = {1996},
series = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
volume = {26},
keywords = {graph coloring problem, surveys}
}
@article{Diaz02,
author = {P. Coll and J. Marenco and I. Mendez-Diaz and P. Zabala},
title = {Facets of the Graph Coloring Polytope},
journal = {Annals of Operations Research},
year = {2002},
volume = {116},
pages = {79--90},
number = {12},
keywords = {graph coloring problem, exact methods}
}