exact.bib
@comment{{This file has been generated by bib2bib 1.95}}
@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,
author = {A. Van Gelder},
title = {Another Look at Graph Coloring via Propositional Satisfiability},
pages = {48--54},
crossref = {symposium02},
keywords = {graph coloring problem, exact methods}
}
@inproceedings{GomShm02,
author = {C. Gomes and D. Shmoys},
title = {Completing Quasigroups or Latin Squares: A Structured Graph Coloring
Problem},
pages = {22--39},
crossref = {symposium02},
keywords = {graph coloring problem, exact methods, applications, instances}
}
@incollection{Sew96,
author = {E.C. Sewell},
title = {An Improved Algorithm for Exact Graph Coloring},
pages = {359--373},
crossref = {dimacs96},
keywords = {graph coloring problem, exact methods}
}
@inproceedings{BarBri02,
author = {N. Barnier and P. Brisset},
title = {Graph Coloring for Air Traffic Flow Management},
booktitle = {CPAIOR'02: Fourth International Workshop on Integration of AI and
OR Techniques in Constraint Programming for Combinatorial Optimisation
Problems},
year = {2002},
pages = {133-147},
address = {Le Croisic, France},
month = {March},
keywords = {graph coloring problem, exact methods, applications},
opturl = {citeseer.nj.nec.com/502256.html}
}
@article{Brown1972,
author = {Brown, J. Randall},
title = {Chromatic Scheduling and the Chromatic Number Problem},
journal = {Management Science},
year = {1972},
volume = {19},
pages = {456--463},
number = {4},
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}
}
@article{Bre79,
author = {D.~Br{\'e}laz},
title = {New Methods to Color the Vertices of a Graph},
journal = {Communications of the ACM},
year = {1979},
volume = {22},
pages = {251--256},
number = {4},
keywords = {graph coloring problem, exact methods}
}
@techreport{Marecek2007TR,
author = {Edmund K. Burke and Jakub Mare{\v c}ek and Andrew J. Parkes and Hana
Rudov{\' a}},
title = {On a Clique-Based Integer Programming Formulation of Vertex Colouring
with Applications in Course Timetabling},
institution = {The University of Nottingham},
year = {2007},
number = {NOTTCS-TR-2007-10},
address = {Nottingham},
keywords = {graph coloring problem, exact methods, applications},
url = {http://arxiv.org/abs/0710.3603}
}
@article{CarDOl02,
author = {Massimiliano Caramia and Paolo Dell'Olmo},
title = {Bounding vertex coloring by truncated {\it multistage} branch and
bound},
journal = {Networks},
year = {2004},
volume = {44},
pages = {231-242},
number = {4},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1002/net.20035},
keywords = {graph coloring problem, exact methods}
}
@article{CarDel01,
author = {Massimiliano Caramia and Paolo Dell'Olmo},
title = {Solving the minimum-weighted coloring problem},
journal = {Networks},
year = {2001},
volume = {38},
pages = {88--101},
number = {2},
keywords = {graph coloring problem, exact methods}
}
@article{DBLP:journals/dam/DesrosiersGH08,
author = {Christian Desrosiers and Philippe Galinier and Alain Hertz},
title = {Efficient algorithms for finding critical subgraphs},
journal = {Discrete Applied Mathematics},
year = {2008},
volume = {156},
pages = {244-266},
number = {2},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1016/j.dam.2006.07.019},
keywords = {graph coloring problem, exact methods}
}
@article{Epp03,
author = {David Eppstein},
title = {Small Maximal Independent Sets and Faster Exact Graph Coloring},
journal = {Journal of Graph Algorithms and Applications},
year = {2003},
volume = {7},
pages = {131-140},
number = {2},
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,
author = {Stefano Gualandi},
title = {Enhancing Constraint Programming-based Column Generation for Integer
Programs},
school = {Dipartimento di Elettronica e Informazione, Politecnico di Milano},
year = {2008},
keywords = {graph coloring problem, exact methods}
}
@article{Gualandi2010,
author = {Stefano Gualandi and Federico Malucelli},
title = {Exact Solution of Graph Coloring Problems via Constraint Programming
and Column Generation},
journal = {INFORMS Journal on Computing},
year = {2011},
note = {Published online},
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,
author = {Pierre Hansen and Martine Labb\'e and David Schindl},
title = {Set covering and packing formulations of graph coloring: Algorithms
and first polyhedral results},
journal = {Discrete Optimization},
year = {2009},
volume = {6},
pages = {135 - 147},
number = {2},
note = {Also as Tec.\ Rep.\ G-2005-76 Cahier du GERAD, Montreal},
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}
}
@unpublished{Held2010,
author = {Stephan Held and Edward C. Sewell and William Cook},
title = {Safe lower bounds for graph coloring},
note = {Accepted at IPCO 2011},
year = {2010},
keywords = {graph coloring problem, lower bounds, exact methods},
owner = {marco},
timestamp = {2010.12.05}
}
@article{HerHer02,
author = {Francine Herrmann and Alain Hertz},
title = {Finding the chromatic number by means of critical graphs},
journal = {Journal of Experimental Algorithmics},
year = {2002},
volume = {7},
pages = {10},
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,
author = {Marek Kubale and Boguslaw Jackowski},
title = {A generalized implicit enumeration algorithm for graph coloring},
journal = {Communications of the ACM},
year = {1985},
volume = {28},
pages = {412--418},
number = {4},
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,
author = {C. Lucet and F. Mendes and A. Moukrim},
title = {An exact method for graph coloring},
journal = {Computers \& Operations Research},
year = {2006},
volume = {33},
pages = {2189--2207},
number = {8},
doi = {doi:10.1016/j.cor.2005.01.008},
keywords = {graph coloring problem, exact methods}
}
@article{Malaguti2010,
author = {Enrico Malaguti and Michele Monaci and Paolo Toth},
title = {An Exact Approach for the Vertex Coloring Problem},
journal = {Discrete Optimization},
year = {2010},
month = {December},
note = {In Press},
keywords = {graph coloring problem, exact methods},
owner = {marco},
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,
author = {A. Mehrotra and M. Trick},
title = {A Column Generation Approach for Graph Coloring},
journal = {INFORMS Journal On Computing},
year = {1996},
volume = {8},
pages = {344--354},
number = {4},
keywords = {graph coloring problem, exact methods, instances}
}
@article{DBLP:journals/dam/Mendez-DiazZ08,
author = {Isabel M{\'e}ndez-D\'{\i}az and Paula Zabala},
title = {A cutting plane algorithm for graph coloring},
journal = {Discrete Applied Mathematics},
year = {2008},
volume = {156},
pages = {159-179},
number = {2},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1016/j.dam.2006.07.010},
keywords = {graph coloring problem, exact methods}
}
@article{MenZab06,
author = {Isabel M{\'e}ndez-D{\'i}az and Paula Zabala},
title = {A Branch-and-Cut algorithm for graph coloring},
journal = {Discrete Applied Mathematics},
year = {2006},
volume = {154},
pages = {826--847},
number = {5},
doi = {doi:10.1016/j.dam.2005.05.022},
keywords = {graph coloring problem, exact methods}
}
@incollection{MenZab01,
author = {Isabel M{\'e}ndez-D{\'i}az and Paula Zabala},
title = {A polyhedral approach for graph coloring},
booktitle = {Electronics Notes in Discrete Mathematics},
publisher = {springer},
year = {2001},
volume = {7},
keywords = {graph coloring problem, exact methods}
}
@article{Pee83,
author = {J. Peem\"oller},
title = {A correction to {B}relaz's modification of {B}rown's coloring algorithm},
journal = {Communications of the ACM archive},
year = {1983},
volume = {26},
pages = {595--597},
number = {8},
month = {August},
keywords = {graph coloring problem, exact methods}
}
@misc{Sch03,
author = {David Schindl},
title = {Graph coloring and linear programming},
month = {July},
year = {2003},
note = {Presentation at First Joint Operations Research Days, Ecole Polytechnique
F\'ed\'erale de Lausanne (EPFL), available on line (last visited
June 2005)},
keywords = {graph coloring problem, exact methods},
url = {http://roso.epfl.ch/ibm/jord03.html}
}
@article{Vas04,
author = {Michel Vasquez},
title = {New Results on the Queens$\_n^2$ Graph Coloring Problem},
journal = {Journal of Heuristics},
year = {2004},
volume = {10},
pages = {407--413},
number = {4},
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},
editor = {D. S. Johnson and A. Mehrotra and M. Trick},
address = {Ithaca, New York, USA},
booktitle = {Proceedings of the Computational Symposium on Graph Coloring and
its Generalizations}
}
@book{dimacs96,
title = {Cliques, Coloring, and Satisfiability: Second {DIMACS} Implementation
Challenge, 1993},
publisher = {American Mathematical Society, Providence, RI, USA},
year = {1996},
editor = {David S. Johnson and Michael Trick},
volume = {26},
series = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
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}
}