Bibliography on Graph-Vertex Coloring
The articles included in this bibliography focus on the problem of
coloring the vertices of large and general graphs.
Publications are organized in the following categories.
If opportune a publication may appear in more than one
category. Entries follow a reverse date order. The list does not aim to
be exhaustive. Last update:
12:59:48, November 12, 2015
[GM12]
|
S. Gualandi, F. Malucelli (2012).
Exact Solution of Graph Coloring Problems via Constraint
Programming and Column Generation.
INFORMS Journal on Computing, vol. 24, no. 1, pp. 81-100.
[ bib |
DOI ]
|
[HCS12]
|
S. Held, W. Cook, E. Sewell (2012).
Maximum-weight stable sets and safe lower bounds for graph
coloring.
Mathematical Programming Computation, vol. 4, no. 4, pp.
363-381.
[ bib |
DOI |
http ]
|
[HCS11]
|
S. Held, W. Cook, E. Sewell (2011).
Safe lower bounds for graph coloring.
Integer Programming and Combinatoral Optimization, pp.
261-273.
[ bib ]
|
[MMT11]
|
E. Malaguti, M. Monaci, P. Toth (2011).
An Exact Approach for the Vertex Coloring Problem.
Discrete Optimization, vol. 8, no. 2, pp. 174-190.
[ bib ]
|
[HLS09]
|
P. Hansen, M. Labbé, D. Schindl (2009).
Set covering and packing formulations of graph coloring:
Algorithms and first polyhedral results.
Discrete Optimization, vol. 6, no. 2, pp. 135 - 147.
Also as Tec. Rep. G-2005-76 Cahier du GERAD, Montreal.
[ bib |
DOI |
.html ]
|
[DGH08]
|
C. Desrosiers, P. Galinier, A. Hertz (2008).
Efficient algorithms for finding critical subgraphs.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 244-266.
[ bib |
DOI ]
|
[Gua08]
|
S. Gualandi (2008).
Enhancing Constraint Programming-based Column Generation for
Integer Programs.
Ph.D. thesis, Dipartimento di Elettronica e Informazione, Politecnico
di Milano.
[ bib ]
|
[MDZ08]
|
I. Méndez-Díaz, P. Zabala (2008).
A cutting plane algorithm for graph coloring.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 159-179.
[ bib |
DOI ]
|
[BMPR07]
|
E. K. Burke, J. Mareček, A. J. Parkes, H. Rudová
(2007).
On a Clique-Based Integer Programming Formulation of Vertex
Colouring with Applications in Course Timetabling.
Tech. Rep. NOTTCS-TR-2007-10, The University of Nottingham,
Nottingham.
[ bib |
http ]
|
[LMM06]
|
C. Lucet, F. Mendes, A. Moukrim (2006).
An exact method for graph coloring.
Computers & Operations Research, vol. 33, no. 8, pp.
2189-2207.
[ bib |
DOI ]
|
[MDZ06]
|
I. Méndez-Díaz, P. Zabala (2006).
A Branch-and-Cut algorithm for graph coloring.
Discrete Applied Mathematics, vol. 154, no. 5, pp. 826-847.
[ bib |
DOI ]
|
[CD04]
|
M. Caramia, P. Dell'Olmo (2004).
Bounding vertex coloring by truncated multistage branch
and bound.
Networks, vol. 44, no. 4, pp. 231-242.
[ bib |
DOI ]
|
[Vas04]
|
M. Vasquez (2004).
New Results on the Queens_n2 Graph Coloring Problem.
Journal of Heuristics, vol. 10, no. 4, pp. 407-413.
[ bib |
DOI ]
|
[Sch03]
|
D. Schindl (2003).
Graph coloring and linear programming.
Presentation at First Joint Operations Research Days, Ecole
Polytechnique Fédérale de Lausanne (EPFL), available on line (last
visited June 2005).
[ bib |
.html ]
|
[Epp03]
|
D. Eppstein (2003).
Small Maximal Independent Sets and Faster Exact Graph
Coloring.
Journal of Graph Algorithms and Applications, vol. 7, no. 2,
pp. 131-140.
[ bib ]
|
[BB02]
|
N. Barnier, P. Brisset (2002).
Graph Coloring for Air Traffic Flow Management.
In CPAIOR'02: Fourth International Workshop on Integration of
AI and OR Techniques in Constraint Programming for Combinatorial Optimisation
Problems, pp. 133-147. Le Croisic, France.
[ bib ]
|
[Gel02]
|
A. V. Gelder (2002).
Another Look at Graph Coloring via Propositional
Satisfiability.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 48-54. Ithaca, New York, USA.
[ bib ]
|
[GS02]
|
C. Gomes, D. Shmoys (2002).
Completing Quasigroups or Latin Squares: A Structured Graph
Coloring Problem.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 22-39. Ithaca, New York, USA.
[ bib ]
|
[HH02]
|
F. Herrmann, A. Hertz (2002).
Finding the chromatic number by means of critical graphs.
Journal of Experimental Algorithmics, vol. 7, p. 10.
[ bib |
DOI ]
|
[CMMDZ02]
|
P. Coll, J. Marenco, I. Mendez-Diaz, P. Zabala (2002).
Facets of the Graph Coloring Polytope.
Annals of Operations Research, vol. 116, no. 12, pp. 79-90.
[ bib ]
|
[CD01]
|
M. Caramia, P. Dell'Olmo (2001).
Solving the minimum-weighted coloring problem.
Networks, vol. 38, no. 2, pp. 88-101.
[ bib ]
|
[MDZ01]
|
I. Méndez-Díaz, P. Zabala (2001).
A polyhedral approach for graph coloring.
In Electronics Notes in Discrete Mathematics, vol. 7.
springer.
[ bib ]
|
[Sew96]
|
E. Sewell (1996).
An Improved Algorithm for Exact Graph Coloring.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 359-373. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[MT96]
|
A. Mehrotra, M. Trick (1996).
A Column Generation Approach for Graph Coloring.
INFORMS Journal On Computing, vol. 8, no. 4, pp. 344-354.
[ bib ]
|
[KJ85]
|
M. Kubale, B. Jackowski (1985).
A generalized implicit enumeration algorithm for graph
coloring.
Communications of the ACM, vol. 28, no. 4, pp. 412-418.
[ bib |
DOI ]
|
[Pee83]
|
J. Peemöller (1983).
A correction to Brelaz's modification of Brown's coloring
algorithm.
Communications of the ACM archive, vol. 26, no. 8, pp.
595-597.
[ bib ]
|
[Bré79]
|
D. Brélaz (1979).
New Methods to Color the Vertices of a Graph.
Communications of the ACM, vol. 22, no. 4, pp. 251-256.
[ bib ]
|
[CG73]
|
D. G. Corneil, B. Graham (1973).
An Algorithm for Determining the Chromatic Number of a
Graph.
SIAM Journal on Computing, vol. 2, no. 4, pp. 311-318.
[ bib ]
|
[Bro72]
|
J. R. Brown (1972).
Chromatic Scheduling and the Chromatic Number Problem.
Management Science, vol. 19, no. 4, pp. 456-463.
[ bib |
http ]
|
[Mar]
|
J. Marecek.
[ bib |
http ]
|
[CGG11]
|
M. Chiarandini, G. Galbiati, S. Gualandi (2011).
Efficiency issues in the RLF heuristic for graph coloring.
In L. D. Gaspero, A. Schaerf, T. Stützle (eds.),
Proceedings of the 9th Metaheuristics International Conference, MIC
2011, pp. 461-469. Dipartimento di Ingegneria Elettrica, Gestionale e
Meccanica, Università di Udine, Udine, Italy.
ISBN 978-88-90084-3-7.
Source code available at
http://www.imada.sdu.dk/~marco/gcp/rlf.
[ bib |
.pdf ]
|
[CS10]
|
M. Chiarandini, T. Stützle (2010).
An Analysis of Heuristics for Vertex Colouring.
In P. Festa (ed.), Experimental Algorithms,
Proceedings of the 9th International Symposium, (SEA 2010), vol. 6049 of
Lecture Notes in Computer Science, pp. 326-337. Springer.
Supplementary material and source code available at
http://www.imada.sdu.dk/~marco/gcp-study/.
[ bib |
DOI ]
|
[Cha04]
|
G. Chaitin (2004).
Register allocation and spilling via graph coloring.
SIGPLAN Not., vol. 39, no. 4, pp. 66-74.
[ bib |
DOI ]
|
[Klo02]
|
W. Klotz (2002).
Graph coloring algorithms.
Tech. Rep. Mathematik-Bericht 5, Clausthal University of Technology,
Clausthal, Germany.
[ bib ]
|
[Pee01]
|
H. A. Peelle (2001).
Graph coloring in J: an introduction.
In Proceedings of the 2001 International Conference on APL: An
Arrays Odyssey, pp. 77-82. Yale University, New Haven, Connecticut, USA.
[ bib |
DOI ]
|
[Veg99]
|
S. R. Vegdahl (1999).
Using node merging to enhance graph coloring.
In PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on
Programming language design and implementation, pp. 150-154. ACM Press, New
York, NY, USA.
ISBN 1-58113-094-5.
[ bib |
DOI ]
|
[dW90]
|
D. de Werra (1990).
Heuristics for Graph Coloring.
Computing Supplement, vol. 7, pp. 191-208.
[ bib ]
|
[Lei79]
|
F. T. Leighton (1979).
A Graph Coloring Algorithm for Large Scheduling Problems.
Journal of Research of the National Bureau of Standards,
vol. 84, no. 6, pp. 489-506.
[ bib ]
|
[Woo69]
|
D. C. Wood (1969).
A Technique for Coloring a Graph Applicable to Large-Scale
Timetabling Problems.
Computer Journal, vol. 12, pp. 317-322.
[ bib ]
|
[CS10]
|
M. Chiarandini, T. Stützle (2010).
An Analysis of Heuristics for Vertex Colouring.
In P. Festa (ed.), Experimental Algorithms,
Proceedings of the 9th International Symposium, (SEA 2010), vol. 6049 of
Lecture Notes in Computer Science, pp. 326-337. Springer.
Supplementary material and source code available at
http://www.imada.sdu.dk/~marco/gcp-study/.
[ bib |
DOI ]
|
[Lew09]
|
R. Lewis (2009).
A general-purpose hill-climbing method for order independent
minimum gr ouping problems: A case study in graph colouring and bin packing.
Computers & Operations Research, vol. 36, no. 7, pp. 2295 -
2310.
[ bib |
DOI |
http ]
|
[BZ08]
|
I. Blöchliger, N. Zufferey (2008).
A graph coloring heuristic using partial solutions and a
reactive tabu scheme.
Computers & Operations Research, vol. 35, no. 3, pp.
960-975.
[ bib |
DOI ]
|
[BNPP08]
|
T. N. Bui, T. H. Nguyen, C. M. Patel, K.-A. T. Phan (2008).
An ant-based algorithm for coloring graphs.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 190-200.
[ bib |
DOI ]
|
[CD08]
|
M. Caramia, P. Dell'Olmo (2008).
Coloring graphs by iterated local search traversing feasible
and infeasible solutions.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 201-217.
[ bib |
DOI ]
|
[CDS08]
|
M. Chiarandini, I. Dumitrescu, T. Stützle (2008).
Very Large-Scale Neighborhood Search: Overview and Case
Studies on Coloring Problems.
In C. Blum, M. J. Blesa, A. Roli, M. Sampels (eds.),
Hybrid Metaheuristics, vol. 114 of Studies in Computational
Intelligence, pp. 117-150. Springer.
[ bib |
DOI ]
|
[GHZ08]
|
P. Galinier, A. Hertz, N. Zufferey (2008).
An adaptive memory algorithm for the k-coloring problem.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 267-279.
[ bib |
DOI ]
|
[HPZ08]
|
A. Hertz, M. Plumettaz, N. Zufferey (2008).
Variable Space Search for Graph Coloring.
Discrete Applied Mathematics, vol. 156, no. 13, pp. 2551 -
2560.
[ bib |
DOI ]
|
[MMT08]
|
E. Malaguti, M. Monaci, P. Toth (2008).
A Metaheuristic Approach for the Vertex Coloring Problem.
INFORMS Journal on Computing, vol. 20, no. 2, pp. p302 - 316.
[ bib |
DOI |
http ]
|
[TY08]
|
P. M. Talaván, J. Yáñez (2008).
The graph coloring problem: A neuronal network approach.
European Journal of Operational Research, vol. 191, no. 1, pp.
100 - 111.
[ bib |
DOI |
http ]
|
[PHK07]
|
D. C. Porumbel, J.-K. Hao, P. Kuntz (2007).
A Study of Evaluation Functions for the Graph K-Coloring
Problem.
In N. Monmarché, E.-G. Talbi, P. Collet,
M. Schoenauer, E. Lutton (eds.), Artificial Evolution, vol. 4926 of
Lecture Notes in Computer Science, pp. 124-135. Springer.
ISBN 978-3-540-79304-5.
[ bib |
DOI ]
|
[TY07]
|
M. A. Trick, H. Yildiz (2007).
A Large Neighborhood Search Heuristic for Graph Coloring.
In P. Van Hentenryck, L. A. Wolsey (eds.),
Integration of AI and OR Techniques in Constraint Programming for
Combinatorial Optimization Problems, vol. 4510 of Lecture Notes in
Computer Science, pp. 346-360. Springer.
ISBN 978-3-540-72396-7.
[ bib |
DOI ]
|
[DT07]
|
K. A. Dowsland, J. M. Thompson (2007).
An improved ant colony optimisation heuristic for graph
colouring.
Discrete Applied Mathematics.
In Press, Corrected Proof.
[ bib |
DOI ]
|
[GHSL07]
|
B. Gendron, A. Hertz, P. St-Louis (2007).
On edge orienting methods for graph coloring.
Journal of combinatorial optimization, vol. 13, no. 2, pp.
163-178.
[ bib |
DOI ]
|
[OYH07]
|
T. Ono, M. Yagiura, T. Hirata (2007).
A vector assignment approach for the graph coloring problem.
In Proc. Learning and Intelligent OptimizatioN Conference (LION
2007 II). Trento, Italy.
To appear as LNCS.
[ bib ]
|
[CDI06]
|
M. Caramia, P. Dell'Olmo, G. F. Italiano (2006).
CHECKCOL: Improved local search for graph coloringstar.
Journal of Discrete Algorithms, vol. 4, no. 2, pp. 277-298.
[ bib |
DOI ]
|
[GPB05]
|
C. A. Glass, A. Prügel-Bennett (2005).
A Polynomially Searchable Exponential Neighbourhood for Graph
Colouring.
Journal of the Operational Research Society, vol. 56, no. 3,
pp. 324-330.
[ bib ]
|
[KGAR05]
|
G. A. Kochenberger, F. Glover, B. Alidaee, C. Rego (2005).
An Unconstrained Quadratic Binary Approach to the Vertex
Coloring Problem.
Annals of Operations Research, vol. 139, no. 1, pp. 229-241.
[ bib ]
|
[DS03]
|
L. Di Gaspero, A. Schaerf (2003).
EasyLocal++: An object-oriented framework for
flexible design of local search algorithms.
Software - Practice & Experience, vol. 33, no. 8, pp.
733-765.
[ bib ]
|
[CNP03]
|
V. Cutello, G. Nicosia, M. Pavone (2003).
A Hybrid Immune Algorithm with Information Gain for the Graph
Coloring Problem.
In E. C.-P. et al. (ed.), Proceedings of the
Genetic and Evolutionary Computation Conference (GECCO-2003), vol. 2723 of
Lecture Notes in Computer Science, pp. 171-182. Springer Verlag,
Berlin, Germany.
ISBN 3-540-40602-6.
[ bib ]
|
[AHZ03]
|
C. Avanthay, A. Hertz, N. Zufferey (2003).
A variable neighborhood search for graph coloring.
European Journal of Operational Research.
[ bib ]
|
[BZ03]
|
I. Blöchliger, N. Zufferey (2003).
A Reactive Tabu Search Using Partial Solutions for the Graph
Coloring Problem.
In D. Kral, J. Sgall (eds.), Coloring graphs from
lists with bounded size of their union: result from Dagstuhl Seminar 03391,
vol. 156 of ITI-Series. Department of Applied Mathematics and
Institute for Theoretical Computer Science, Prague.
[ bib ]
|
[BJH03]
|
A. D. Blas, A. Jagota, R. Hughey (2003).
A Range-Compaction Heuristic for Graph Coloring.
Journal of Heuristics, vol. 9, no. 3, pp. 489-506.
[ bib ]
|
[CDS03]
|
M. Chiarandini, I. Dumitrescu, T. Stützle (2003).
Local Search for the Graph Colouring Problem. A
Computational Study.
Tech. Rep. AIDA-03-01, Intellectics Group, Computer Science
Department, Darmstadt University of Technology, Darmstadt, Germany.
[ bib |
.pdf ]
|
[CS02]
|
M. Chiarandini, T. Stützle (2002).
An application of Iterated Local Search to Graph Coloring.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 112-125. Ithaca, New York, USA.
[ bib |
.pdf ]
|
[AKL02]
|
M. Allen, G. Kumaran, T. Liu (2002).
A Combined Algorithm for Graph-coloring in Register
Allocation.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 100-111. Ithaca, New York, USA.
[ bib ]
|
[BP02]
|
T. N. Bui, C. M. Patel (2002).
An Ant System Algorithm for Coloring Graphs.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 83-91. Ithaca, New York, USA.
[ bib ]
|
[PS02b]
|
V. Phan, S. Skiena (2002).
Coloring Graphs With a General Heuristic Search Engine.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 92-99. Ithaca, New York, USA.
[ bib ]
|
[DBJH02]
|
A. Di Blas, A. Jagota, R. Hughey (2002).
Energy function-based approaches to graph coloring.
Neural Networks, IEEE Transactions on, vol. 13, no. 1, pp. 81
-91.
[ bib |
DOI ]
|
[FH02]
|
A. Fabrikant, T. Hogg (2002).
Graph Coloring with Quantum Heuristics.
In Proceedings of the Eighteenth National Conference on
Artificial Intelligence and Fourteenth Conference on Innovative Applications
of Artificial Intelligence, Edmonton, Alberta, Canada. AAAI Press, pp.
22-27.
[ bib ]
|
[GVL02]
|
J. González-Velarde, M. Laguna (2002).
Tabu Search with Simple Ejection Chains for Coloring Graphs.
Annals of Operations Research, vol. 117, no. 1-4, pp.
165-174.
[ bib ]
|
[PS02a]
|
L. Paquete, T. Stützle (2002).
An Experimental Investigation of Iterated Local Search for
Coloring Graphs.
In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf,
G. Raidl (eds.), Applications of Evolutionary Computing, vol. 2279 of
Lecture Notes in Computer Science, pp. 122-131. Springer Verlag,
Berlin, Germany.
[ bib ]
|
[Wal01]
|
C. Walshaw (2001).
A Multilevel Approach to the Graph Colouring Problem.
Tech. Rep. 01/IM/69, School of Computing and Mathematical Science,
Univeristy of Greenwich, London, UK.
[ bib ]
|
[HH01b]
|
J.-P. Hamiez, J.-K. Hao (2001).
Scatter Search for Graph Coloring.
In P. Collet, C. Fonlupt, J.-K. Hao, E. Lutton,
M. Schoenauer (eds.), Artificial Evolution, vol. 2310 of
Lecture Notes in Computer Science, pp. 168-179.
[ bib ]
|
[HH01a]
|
J.-P. Hamiez, J.-K. Hao (2001).
Experimental Investigation of Scatter Search for Graph
Coloring.
In Proceedings of the Metaheuristics International Conference,
pp. 311-316. Porto, Portugal.
[ bib ]
|
[LM01]
|
M. Laguna, R. Martí (2001).
A GRASP for Coloring Sparse Graphs.
Computational optimization and applications, vol. 19, no. 2,
pp. 165-178.
[ bib |
DOI ]
|
[FH00]
|
N. Funabiki, T. Higashino (2000).
A minimal-state processing search algorithm for graph
coloring problems.
IEICE Transactions on Fundamentals, vol. E83-A, no. 7, pp.
1420-1430.
[ bib ]
|
[KP98]
|
D. Kirovski, M. Potkonjak (1998).
Efficient coloring of a large spectrum of graphs.
In DAC '98: Proceedings of the 35th annual conference on Design
automation, pp. 427-432. ACM Press, New York, NY, USA.
ISBN 0-89791-964-5.
[ bib |
DOI ]
|
[Stü98]
|
T. Stützle (1998).
Local Search Algorithms for Combinatorial Problems -
Analysis, Improvements, and New Applications.
Ph.D. thesis, FB Informatik, Technische Universität Darmstadt,
Darmstadt, Germany.
[ bib ]
|
[DH97]
|
C. D., A. Hertz (1997).
Ants Can Colour Graphs.
Journal of the Operational Research Society, vol. 48, pp.
295-305.
[ bib ]
|
[FF96]
|
C. Fleurent, J. Ferland (1996).
Object-oriented implementation of heuristics search methods
for Graph Coloring, Maximum Clique, and Satisfiability.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 619-652. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[LC96]
|
G. Lewandowski, A. Condon (1996).
Experiments with parallel graph coloring heuristics and
applications of graph coloring.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 309-334. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[Mor96]
|
C. Morgenstern (1996).
Distributed Coloration Neighborhood Search.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 335-357. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[Jag96]
|
A. Jagota (1996).
An adaptive, multiple restarts neural network algorithm for
graph coloring.
European Journal of Operational Research, vol. 93, no. 2, pp.
257-270.
[ bib ]
|
[Cul92]
|
J. Culberson (1992).
Iterated Greedy Graph Coloring and the Difficulty Landscape.
Tech. Rep. 92-07, Department of Computing Science, The University of
Alberta, Edmonton, Alberta, Canada.
[ bib ]
|
[Her91]
|
A. Hertz (1991).
COSINE: A new graph coloring algorithm.
Operations Research Letters, vol. 10, no. 7, pp. 411-415.
[ bib |
DOI ]
|
[JAMS91]
|
D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon (1991).
Optimization by Simulated Annealing: An Experimental
Evaluation; Part II, Graph Coloring and Number Partitioning.
Operations Research, vol. 39, no. 3, pp. 378-406.
[ bib ]
|
[MS90]
|
C. Morgenstern, H. Shapiro (1990).
Coloration neighborhood structures for general graph
coloring.
In Proceedings of the first annual ACM-SIAM Symposium on
Discrete algorithms, pp. 226-235. Society for Industrial and Applied
Mathematics, Philadelphia, PA, USA.
ISBN 0-89871-251-3.
[ bib ]
|
[Hd87]
|
A. Hertz, D. de Werra (1987).
Using Tabu Search Techniques for Graph Coloring.
Computing, vol. 39, no. 4, pp. 345-351.
[ bib ]
|
[WH12]
|
Q. Wu, J.-K. Hao (2012).
Coloring large graphs based on independent set extraction.
Computers & Operations Research, vol. 39, no. 2, pp. 283 -
290.
[ bib |
DOI ]
|
[GHZ08]
|
P. Galinier, A. Hertz, N. Zufferey (2008).
An adaptive memory algorithm for the k-coloring problem.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 267-279.
[ bib |
DOI ]
|
[DS03]
|
L. Di Gaspero, A. Schaerf (2003).
EasyLocal++: An object-oriented framework for
flexible design of local search algorithms.
Software - Practice & Experience, vol. 33, no. 8, pp.
733-765.
[ bib ]
|
[BZ03]
|
I. Blöchliger, N. Zufferey (2003).
A Reactive Tabu Search Using Partial Solutions for the Graph
Coloring Problem.
In D. Kral, J. Sgall (eds.), Coloring graphs from
lists with bounded size of their union: result from Dagstuhl Seminar 03391,
vol. 156 of ITI-Series. Department of Applied Mathematics and
Institute for Theoretical Computer Science, Prague.
[ bib ]
|
[CDS03]
|
M. Chiarandini, I. Dumitrescu, T. Stützle (2003).
Local Search for the Graph Colouring Problem. A
Computational Study.
Tech. Rep. AIDA-03-01, Intellectics Group, Computer Science
Department, Darmstadt University of Technology, Darmstadt, Germany.
[ bib |
.pdf ]
|
[CS02]
|
M. Chiarandini, T. Stützle (2002).
An application of Iterated Local Search to Graph Coloring.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 112-125. Ithaca, New York, USA.
[ bib |
.pdf ]
|
[PS02]
|
L. Paquete, T. Stützle (2002).
An Experimental Investigation of Iterated Local Search for
Coloring Graphs.
In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf,
G. Raidl (eds.), Applications of Evolutionary Computing, vol. 2279 of
Lecture Notes in Computer Science, pp. 122-131. Springer Verlag,
Berlin, Germany.
[ bib ]
|
[Wal01]
|
C. Walshaw (2001).
A Multilevel Approach to the Graph Colouring Problem.
Tech. Rep. 01/IM/69, School of Computing and Mathematical Science,
Univeristy of Greenwich, London, UK.
[ bib ]
|
[FH00]
|
N. Funabiki, T. Higashino (2000).
A minimal-state processing search algorithm for graph
coloring problems.
IEICE Transactions on Fundamentals, vol. E83-A, no. 7, pp.
1420-1430.
[ bib ]
|
[KP98]
|
D. Kirovski, M. Potkonjak (1998).
Efficient coloring of a large spectrum of graphs.
In DAC '98: Proceedings of the 35th annual conference on Design
automation, pp. 427-432. ACM Press, New York, NY, USA.
ISBN 0-89791-964-5.
[ bib |
DOI ]
|
[FF96]
|
C. Fleurent, J. Ferland (1996).
Object-oriented implementation of heuristics search methods
for Graph Coloring, Maximum Clique, and Satisfiability.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 619-652. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[LC96]
|
G. Lewandowski, A. Condon (1996).
Experiments with parallel graph coloring heuristics and
applications of graph coloring.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 309-334. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[Jag96]
|
A. Jagota (1996).
An adaptive, multiple restarts neural network algorithm for
graph coloring.
European Journal of Operational Research, vol. 93, no. 2, pp.
257-270.
[ bib ]
|
[Cul92]
|
J. Culberson (1992).
Iterated Greedy Graph Coloring and the Difficulty Landscape.
Tech. Rep. 92-07, Department of Computing Science, The University of
Alberta, Edmonton, Alberta, Canada.
[ bib ]
|
[TC11a]
|
O. Titiloye, A. Crispin (2011).
Graph Coloring with a Distributed Hybrid Quantum Annealing
Algorithm.
In J. O'Shea, N. Nguyen, K. Crockett, R. Howlett,
L. Jain (eds.), Agent and Multi-Agent Systems: Technologies and
Applications, vol. 6682 of Lecture Notes in Computer Science, pp.
553-562. Springer Berlin / Heidelberg.
ISBN 978-3-642-21999-3.
[ bib |
DOI ]
|
[TC11b]
|
O. Titiloye, A. Crispin (2011).
Quantum annealing of the graph coloring problem.
Discrete Optimization, vol. 8, no. 2, pp. 376 - 384.
[ bib |
DOI ]
|
[LH10]
|
Z. Lü, J.-K. Hao (2010).
A memetic algorithm for graph coloring.
European Journal of Operational Research, vol. 203, no. 1, pp.
241 - 250.
[ bib |
DOI ]
|
[PSZ10]
|
M. Plumettaz, D. Schindl, N. Zufferey (2010).
Ant Local Search and its efficient adaptation to graph
colouring.
Journal of Operational Research Society, vol. 61, no. 5, pp.
819 - 826.
[ bib |
DOI ]
|
[PHK10]
|
D. C. Porumbel, J.-K. Hao, P. Kuntz (2010).
An evolutionary approach with diversity guarantee and
well-informed grouping recombination for graph coloring.
Computers & Operations Research, vol. 37, pp. 1822 - 1832.
[ bib |
DOI ]
|
[XL09]
|
X.-F. Xie, J. Liu (2009).
Graph coloring by multiagent fusion search.
Journal of Combinatorial Optimization, vol. 18, no. 2, pp.
99-123.
[ bib |
DOI ]
|
[PHK09]
|
D. Porumbel, J.-K. Hao, P. Kuntz (2009).
Diversity Control and Multi-Parent Recombination for
Evolutionary Graph Coloring Algorithms.
In 9th European Conference on Evolutionary Computation in
Combinatorial Optimisation (Evocop 2009). Tübingen, Germany.
[ bib |
.pdf ]
|
[BNPP08]
|
T. N. Bui, T. H. Nguyen, C. M. Patel, K.-A. T. Phan (2008).
An ant-based algorithm for coloring graphs.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 190-200.
[ bib |
DOI ]
|
[MMT08]
|
E. Malaguti, M. Monaci, P. Toth (2008).
A Metaheuristic Approach for the Vertex Coloring Problem.
INFORMS Journal on Computing, vol. 20, no. 2, pp. p302 - 316.
[ bib |
DOI |
http ]
|
[DT07]
|
K. A. Dowsland, J. M. Thompson (2007).
An improved ant colony optimisation heuristic for graph
colouring.
Discrete Applied Mathematics.
In Press, Corrected Proof.
[ bib |
DOI ]
|
[TW07]
|
E.-G. Talbi, B. Weinberg (2007).
Breaking the search space symmetry in partitioning problems:
An application to the graph coloring problem.
Theoretical Computer Science, vol. 378, no. 1, pp. 78 - 86.
[ bib |
DOI ]
|
[CGG05]
|
C. Croitoru, O. Gheorghies, A. Gheorghies (2005).
An Ordering-Based Genetic Approach to Graph Coloring.
Tech. Rep. TR 05-03, “Al.I.Cuza” University of Iasi, Faculty
of Computer Science.
[ bib ]
|
[GPB03]
|
C. A. Glass, A. Prügel-Bennett (2003).
Genetic Algorithms for Graph Colouring: Exploration of
Galinier and Hao's Algorithm.
Journal of Combinatorial Optimization, vol. 7, no. 3, pp.
229-236.
[ bib ]
|
[BP02]
|
T. N. Bui, C. M. Patel (2002).
An Ant System Algorithm for Coloring Graphs.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 83-91. Ithaca, New York, USA.
[ bib ]
|
[CLGA02]
|
C. Croitoru, H. Luchian, O. Gheorghies, A. Apetrei (2002).
A New Genetic Graph Coloring Heuristic.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 63-74. Ithaca, New York, USA.
[ bib ]
|
[GHZ02]
|
P. Galinier, A. Hertz, N. Zufferey (2002).
Adaptive Memory Algorithms for Graph Colouring.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 75-82. Ithaca, New York, USA.
Also available as Technical Report G-2003-35, Les Cachiers du
GERAD.
[ bib ]
|
[FLS01]
|
D. Fotakis, S. D. Likothanassis, S. Stefanakos (2001).
An Evolutionary Annealing Approach to Graph Coloring.
In E. J. W. Boers, J. Gottlieb, P. L. Lanzi, R. E.
Smith, S. Cagnoni, E. Hart, G. R. Raidl, H. Tijink (eds.),
Applications of Evolutionary Computing, EvoWorkshops 2001, vol. 2037
of Lecture Notes in Computer Science, pp. 120-129. Springer.
[ bib ]
|
[LF01]
|
L. A. N. Lorena, J. C. Furtado (2001).
Constructive Genetic Algorithm for Clustering Problems.
Evolutionary Computation, vol. 9, no. 3, pp. 309-328.
[ bib ]
|
[MD00]
|
A. Marino, R. I. Damper (2000).
Breaking the Symmetry of the Graph Colouring Problem with
Genetic Algorithms.
In D. Whitley (ed.), Late Breaking Papers at the
2000 Genetic and Evolutionary Computation Conference, pp. 240-245. Las
Vegas, Nevada, USA.
[ bib ]
|
[GH99]
|
P. Galinier, J. Hao (1999).
Hybrid evolutionary algorithms for graph coloring.
Journal of Combinatorial Optimization, vol. 3, no. 4, pp.
379-397.
[ bib |
DOI ]
|
[DH98]
|
R. Dorne, J. Hao (1998).
A New Genetic Local Search Algorithm for Graph Coloring.
In A. E. Eiben, T. Bäck, M. Schoenauer, H.-P.
Schwefel (eds.), Parallel Problem Solving from Nature - PPSN V, 5th
International Conference, vol. 1498 of Lecture Notes in Computer
Science, pp. 745-754. Springer Verlag, Berlin, Germany.
[ bib ]
|
[EHH98]
|
A. E. Eiben, J. K. V. D. Hauw, J. I. V. Hemert (1998).
Graph Coloring with Adaptive Evolutionary Algorithms.
Journal of Heuristics, vol. 4, no. 1, pp. 25-46.
[ bib |
DOI ]
|
[DH97]
|
C. D., A. Hertz (1997).
Ants Can Colour Graphs.
Journal of the Operational Research Society, vol. 48, pp.
295-305.
[ bib ]
|
[Mor96]
|
C. Morgenstern (1996).
Distributed Coloration Neighborhood Search.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 335-357. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[FF96]
|
C. Fleurent, J. Ferland (1996).
Genetic and Hybrid Algorithms for Graph Coloring.
Annals of Operations Research, vol. 63, pp. 437-464.
[ bib ]
|
[CHD95]
|
D. Costa, A. Hertz, O. Dubuis (1995).
Embedding of a Sequential Procedure within an Evolutionary
Algorithm for Coloring Problems in Graphs.
Journal of Heuristics, vol. 1, no. 1, pp. 105-128.
[ bib ]
|
[Dav91]
|
L. Davis (1991).
Order-based Genetic Algorithms and the Graph Coloring
Problem.
In Handbook of Genetic Algorithms, pp. 72-90. Van Nostrand
Reinhold; New York.
[ bib ]
|
[DR08]
|
I. Dukanovic, F. Rendl (2008).
A semidefinite programming-based heuristic for graph
coloring.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 180-189.
[ bib |
DOI ]
|
[Gel08]
|
A. V. Gelder (2008).
Another look at graph coloring via propositional
satisfiability.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 230-243.
[ bib |
DOI ]
|
[Pre08]
|
S. D. Prestwich (2008).
Generalised graph colouring by a hybrid of local search and
constraint programming.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 148-158.
[ bib |
DOI ]
|
[DR05]
|
I. Dukanovic, F. Rendl (2005).
A semidefinite programming based heuristic for graph
coloring.
Working paper available through the Optimization Online repository.
Universitaet Klagenfurt, Institut für Mathematik.
[ bib ]
|
[CD02]
|
M. Caramia, P. Dell'Olmo (2002).
Constraint Propagation in Graph Coloring.
Journal of Heuristics, vol. 8, no. 1, pp. 83-107.
[ bib ]
|
[CD99]
|
M. Caramia, P. Dell'Olmo (1999).
A Fast and Simple Local Search for Graph Coloring.
In J. S. Vitter, C. D. Zaroliagis (eds.),
Algorithm Engineering, 3rd International Workshop, WAE '99, London, UK,
July 19-21, 1999, Proceedings, vol. 1668 of Lecture Notes in Computer
Science, pp. 316-329. Springer Verlag, Berlin, Germany.
[ bib ]
|
[GPR96]
|
F. Glover, M. Parker, J. Ryan (1996).
Coloring by Tabu Branch and Bound.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 285-307. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[RA96]
|
C. P. Ravikumar, R. Aggarwal (1996).
Parallel search-and-learn techniques and graph coloring.
Knowledge-Based Systems, vol. 9, no. 1, pp. 3 - 13.
[ bib |
DOI |
http ]
|
[TW07]
|
E.-G. Talbi, B. Weinberg (2007).
Breaking the search space symmetry in partitioning problems:
An application to the graph coloring problem.
Theoretical Computer Science, vol. 378, no. 1, pp. 78 - 86.
[ bib |
DOI ]
|
[TH06]
|
Y. Takenaga, K. Higashide (2006).
Vertex Coloring of Comparability+e and -e
Graphs.
In F. V. Fomin (ed.), Graph-Theoretic Concepts in
Computer Science, vol. 4271 of Lecture Notes in Computer Science, pp.
102-112. Springer Verlag, Berlin, Germany.
[ bib |
DOI ]
|
[CE05]
|
K. Cameron, J. Edmonds (2005).
Colouring Some Classes of Perfect Graphs Robustly.
Electronic Notes in Discrete Mathematics, vol. 22, pp.
553-556.
[ bib |
DOI ]
|
[NW05]
|
J. Nešetřil, G. Woeginger (eds.) (2005).
Graph Colorings, Dagstuhl, Germany, 2003, vol. 349.
[ bib ]
|
[Bol04]
|
B. Bollobás (2004).
Random graphs.
Cambridge studies in advanced mathematics. Cambridge University
Press, Cambridge, UK, second edn.
[ bib ]
|
[Chv04]
|
V. Chvátal (2004).
Coloring the queen graphs.
Web repository (last visited July 2005).
[ bib |
.html ]
|
[Gol04]
|
M. C. Golumbic (2004).
Algorithmic graph theory and perfect graphs.
Elsevier, 2 edn.
[ bib ]
|
[Gon04]
|
G. Gonthier (2004).
A computer-checked proof of the four-colour theorem.
Available online (Last visited July 2005).
[ bib |
http ]
|
[MR02]
|
M. Molloy, B. Reed (2002).
Graph colouring and the probabilistic method, vol. 23 of
Algorithms and Combinatorics.
Springer, Berlin, xiv+326 pp.
[ bib ]
|
[Die00]
|
R. Diestel (2000).
Graph Theory.
Springer, Berlin, second ed., electronic edn.
[ bib ]
|
[AKS99]
|
N. Alon, M. Krivelevich, B. Sudakov (1999).
Coloring graphs with sparse neighborhoods.
Journal of Combinatorial Theory, Ser. B, vol. 77, pp. 73-82.
[ bib ]
|
[BLS99]
|
A. Brandstädt, V. B. Le, J. P. Spinrad (1999).
Graph Classes: A Survey, vol. 3 of Monographs on
Discrete Mathematics and Applications.
SIAM Society for Industrial and Applied Mathematics, Philadelphia.
[ bib ]
|
[RSST96]
|
N. Robertson, D. P. Sanders, P. Seymour, R. Thomas (1996).
A new proof of the four-colour theorem.
Electronic Research Announcements of the American Mathematical
Society, vol. 2, no. 1, pp. 17-25.
[ bib ]
|
[JT94]
|
T. R. Jensen, B. Toft (1994).
Graph Coloring Problems.
John Wiley & Sons, New York, NY, USA.
[ bib ]
|
[Knu94]
|
D. E. Knuth (1994).
The Sandwich Theorem.
Electron. J. Combin., vol. 1, pp. Article 1, approx. 48 pp. (electronic).
[ bib |
.pdf ]
|
[Luc91]
|
T. Luczak (1991).
The chromatic number of random graphs.
Combinatorica, vol. 11, no. 1, pp. 45-54.
[ bib ]
|
[VL88]
|
R. Venkatesan, L. Levin (1988).
Random instances of a graph coloring problem are hard.
In STOC '88: Proceedings of the twentieth annual ACM symposium
on Theory of computing, pp. 217-222. ACM Press, New York, NY, USA.
ISBN 0-89791-264-0.
[ bib |
DOI ]
|
[BT85]
|
B. Bollobás, A. Thomason (1985).
Random graphs of small order.
Annals of Discrete Mathematics, vol. 28, pp. 251-256.
[ bib ]
|
[JM82]
|
A. Johri, D. Matula (1982).
Probabilistic Bounds and Heuristic Algorihms for Coloring
Large Random Graphs.
Tech. Rep. 82-CSE-6, Southern Methodist University, Dallas, Texas,
USA.
[ bib ]
|
[GLS81]
|
M. Grötschel, L. Lovász, A. Schrijver (1981).
The ellipsoid method and its consequences in combinatorial
optimization.
Combinatorica, vol. 1, no. 2, pp. 169-197.
[ bib ]
|
[GJMP80]
|
M. R. Garey, D. S. Johnson, G. L. Miller, C. H. Papadimitriou
(1980).
The Complexity of Coloring Circular Arcs and Chords.
SIAM Journal of Algebraic and Discrete Methods, vol. 1, pp.
216-227.
[ bib ]
|
[GJ79]
|
M. R. Garey, D. S. Johnson (1979).
Computers and Intractability: A Guide to the Theory of
NP-Completeness.
Freeman, San Francisco, CA, USA.
[ bib ]
|
[Lov79]
|
L. Lovász (1979).
On the Shannon capacity of a graph.
IEEE Transactions on Information Theory, vol. 25, pp. 1-7.
[ bib ]
|
[AHK77]
|
K. Appel, W. Haken, J. Koch (1977).
Every planar map is four colorable.
Illinois Journal of Mathematics, vol. 21, pp. 429-567.
[ bib ]
|
[GJ76]
|
M. R. Garey, D. S. Johnson (1976).
The Complexity of Near Optimal Graph Coloring.
Journal of the Association for Computing Machinery, vol. 23,
pp. 43-49.
[ bib ]
|
[Joh74]
|
D. S. Johnson (1974).
Worst-case behavior of graph-coloring algorithms.
In F. Hoffman, R. Kingsley, R. Levow, R. Mullin,
R. Thomas (eds.), South-Eastern Conference on Combinatorics, Graph
Theory and Computing, vol. X of Congressus Numerantium, pp. 513-528.
Utilitas Mathematica Publishing, Winnipeg, Canada.
[ bib ]
|
[Sto73]
|
L. Stockmeyer (1973).
Planar 3-Colorability is NP-Complete.
SIGACT News, vol. 5, no. 3, pp. 19-25.
[ bib ]
|
[Kar72]
|
R. M. Karp (1972).
Reducibility among combinatorial problems.
In R. E. Miller, J. W. Thatcher (eds.),
Complexity of Computer Computations, pp. 85-103. Plenum Press, New
York, USA.
[ bib ]
|
[Erd61]
|
P. Erdős (1961).
Graph theory and probability II.
Canadian Journal of Mathematics, vol. 13, pp. 346-352.
[ bib ]
|
[AN05]
|
D. Achlioptas, A. Naor (2005).
The Two Possible Values of the Chromatic Number of a Random
Graph.
To appear in Annals of Mathematics.
[ bib ]
|
[COT04]
|
A. Coja-Oghlan, A. Taraz (2004).
Exact and approximative algorithms for coloring G(n, p).
Random structures & algorithms, vol. 24, no. 3, pp. 259-278.
[ bib |
DOI ]
|
[CV04]
|
P. Crescenzi, K. Viggo (2004).
A compendium of NP optimization problems.
Available online (last visited February 2005).
[ bib |
.html ]
|
[GRS03]
|
C. Gomes, R. Regis, D. Shmoys (2003).
An Improved Approximation for the Partial Latin Square
Extension Problem.
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on
Discrete Algorithms. Baltimore, Maryland, USA.
[ bib ]
|
[Pas03]
|
V. T. Paschos (2003).
Polynomial approximation and graph-coloring.
Computing, vol. 70, no. 1, pp. 41-86.
[ bib |
DOI ]
|
[BGS98]
|
M. Bellare, O. Goldreich, M. Sudan (1998).
Free Bits, PCPs, and Nonapproximability-Towards Tight
Results.
SIAM Journal on Computing, vol. 27, no. 3, pp. 804-915.
[ bib |
DOI ]
|
[FK98]
|
U. Feige, J. Kilian (1998).
Zero Knowledge and the Chromatic Number.
Journal of Computer and System Sciences, vol. 57, no. 2, pp.
187-199.
[ bib ]
|
[Hal93]
|
M. M. Halldórsson (1993).
A still better performance guarantee for approximate graph
coloring.
Information Processing Letters, vol. 45, no. 1, pp. 19-23.
[ bib |
DOI ]
|
[BR90]
|
B. Berger, J. Rompel (1990).
A better performance guarantee for approximate graph
colouring.
Algorithmica, vol. 5, no. 4, pp. 459-466.
[ bib ]
|
[Wig83]
|
A. Wigderson (1983).
Improving the performance guarantee for approximate graph
coloring.
Journal of the ACM, vol. 30, no. 4, pp. 729-735.
[ bib |
DOI ]
|
[Wig82]
|
A. Wigderson (1982).
A new approximate graph coloring algorithm.
In Proceedings of the Fourteenth Annual ACM Symposium on Theory
of Computing, pp. 325-329.
[ bib ]
|
[Joh74]
|
D. S. Johnson (1974).
Approximation Algorithms for Combinatorial Problems.
Journal of Computer and System Sciences, vol. 9, pp. 256-278.
[ bib ]
|
[HCS11]
|
S. Held, W. Cook, E. Sewell (2011).
Safe lower bounds for graph coloring.
Integer Programming and Combinatoral Optimization, pp.
261-273.
[ bib ]
|
[DR07]
|
I. Dukanovic, F. Rendl (2007).
Semidefinite programming relaxations for graph coloring and
maximal clique problems.
Mathematical Programming, Serie B, vol. 109, no. 2-3, pp.
345-365.
[ bib |
DOI ]
|
[GL07b]
|
N. Gvozdenović, M. Laurent (2007).
The operator Ψ for the Chromatic Number of a Graph.
Optimization Online.
[ bib |
.html ]
|
[GL07a]
|
N. Gvozdenović, M. Laurent (2007).
Computing semidefinite programming lower bounds for the
(fractional) chromatic number via block-diagonalization.
Optimization Online.
[ bib |
.html ]
|
[LTMG12]
|
R. Lewis, J. Thompson, C. Mumford, J. Gillard (2012).
A wide-ranging computational comparison of high-performance
graph colouring algorithms.
Computers & Operations Research, vol. 39, no. 9, pp. 1933
- 1950.
[ bib |
DOI |
http ]
|
[PHK10]
|
D. C. Porumbel, J.-K. Hao, P. Kuntz (2010).
A search space "cartography" for guiding graph coloring
heuristics.
Computers & Operations Research, vol. 37, no. 4, pp. 769 -
778.
[ bib |
DOI ]
|
[Chi05]
|
M. Chiarandini (2005).
Stochastic Local Search Methods for Highly Constrained
Combinatorial Optimisation Problems.
Ph.D. thesis, Computer Science Department, Darmstadt University of
Technology, Darmstadt, Germany.
[ bib |
.pdf ]
|
[GS05]
|
C. Gomes, B. Selman (2005).
Can Get Satisfaction.
Nature, vol. 435, pp. 751-752.
[ bib ]
|
[BF04]
|
V. C. Barbosa, R. G. Ferreira (2004).
On the phase transitions of graph coloring and independent
sets.
Physica A: Statistical Mechanics and its Applications, vol.
343, no. 1-2.
[ bib ]
|
[HH04]
|
J.-P. Hamiez, J.-K. Hao (2004).
An analysis of solution properties of the graph coloring
problem.
In M. G. C. Resende, J. P. de Sousa, A. Viana (eds.),
Metaheuristics: computer decision-making, pp. 325-345. Kluwer
Academic Publishers, Norwell, MA, USA.
ISBN 1-4020-7653-3.
[ bib ]
|
[Wal02]
|
T. Walsh (2002).
2+p-COL.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 17-22. Ithaca, New York, USA.
[ bib ]
|
[MPWZ02]
|
R. Mulet, A. Pagnani, M. Weigt, R. Zecchina (2002).
Coloring random graphs.
Physical Review Letters, vol. 89, no. 26.
[ bib ]
|
[CG01]
|
J. Culberson, I. P. Gent (2001).
Frozen Development in Graph Coloring.
Theoretical Computer Science, vol. 265, no. 1-2.
[ bib ]
|
[Cul01]
|
J. Culberson (2001).
Hidden Solutions, Tell-tales, Heuristics and
Anti-heuristics.
In H. Hoos, T. Stuëtzle (eds.), The IJCAI-01
Workshop on Empirical Methods in Artificial Intelligence, pp. 9-14.
[ bib ]
|
[HH01]
|
J.-P. Hamiez, J.-K. Hao (2001).
An analysis of solution properties of the graph coloring
problem.
In Proceedings of the Metaheuristics International Conference,
pp. 193-198. Porto, Portugal.
[ bib ]
|
[Sve01]
|
P. Svenson (2001).
From Neel to NPC: Colouring Small Worlds.
Computing Research Repository, vol. cs.CC/0107015.
[ bib ]
|
[Wal01]
|
T. Walsh (2001).
Search on High Degree Graphs.
In B. Nebel (ed.), Proceedings of the 1st
International Joint Conference on Artificial Intelligence, pp. 266-274.
Morgan Kaufmann, Seattle, Washington, USA.
[ bib ]
|
[CG99]
|
J. Culberson, I. P. Gent (1999).
Well out of reach: Why hard problems are hard.
Tech. Rep. APES-13-1999, APES (Algorithms, Problems, and Empirical
Studies) Group.
[ bib ]
|
[Wal99]
|
T. Walsh (1999).
Search in a Small World.
In T. Dean (ed.), Proceedings of the 16th
International Joint Conference on Artificial Intelligence, pp. 1172-1177.
Morgan Kaufmann, Stockholm, Sweden.
[ bib ]
|
[SN98]
|
P. Svenson, M. G. Nordahl (1998).
Relaxation in graph coloring and satisfiability problems.
Computing Research Repository, vol. cond-mat/9810144.
[ bib ]
|
[Cou97]
|
O. Coudert (1997).
Exact coloring of real-life graphs is easy.
In DAC '97: Proceedings of the 34th annual conference on Design
automation, pp. 121-126. ACM Press, New York, NY, USA, New York, NY, USA.
ISBN 0-89791-920-3.
[ bib |
DOI ]
|
[CL96]
|
J. Culberson, F. Luo (1996).
Exploring the k-colorable Landscape with Iterated Greedy.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 245-284. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[Hog96]
|
T. Hogg (1996).
Refining the Phase Transition in Combinatorial Search.
Artificial Intelligence, vol. 81, no. 1-2, pp. 127-154.
[ bib ]
|
[CBP95]
|
J. Culberson, A. Beacham, D. Papp (1995).
Hiding our Colors.
In Proceedings of the CP'95 Workshop on Studying and Solving
Really Hard Problems, pp. 31-42. Cassis, France.
[ bib |
.html ]
|
[HJdAa94]
|
A. Hertz, B. Jaumard, M. P. de Aragão (1994).
Local optima topology for the k-coloring problem.
Discrete Applied Mathematics, vol. 49, no. 1-3, pp. 257-280.
[ bib |
DOI ]
|
[Cul92]
|
J. Culberson (1992).
Iterated Greedy Graph Coloring and the Difficulty Landscape.
Tech. Rep. 92-07, Department of Computing Science, The University of
Alberta, Edmonton, Alberta, Canada.
[ bib ]
|
[CKT91]
|
P. Cheeseman, B. Kanefsky, W. M. Taylor (1991).
Where the Really Hard Problems Are.
In J. Mylopoulos, R. Reiter (eds.), Proceedings
of the 12th International Joint Conference on Artificial Intelligence, pp.
331-337. Morgan Kaufmann Publishers, San Francisco, CA, USA.
[ bib ]
|
[LT10]
|
R. Lewis, J. Thompson (2010).
On the application of graph colouring techniques in
round-robin sports scheduling.
Computers & Operations Research, vol. In Press, Corrected
Proof, pp. -.
[ bib |
DOI |
http ]
|
[HS08]
|
S. Hossain, T. Steihaug (2008).
Graph coloring in the estimation of sparse derivative
matrices: Instances and applications.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 280-288.
[ bib |
DOI ]
|
[ZAG08]
|
N. Zufferey, P. Amstutz, P. Giaccari (2008).
Graph Colouring Approaches for a Satellite Range Scheduling
Problem.
Journal of Scheduling, vol. 11, no. 4, pp. 263 - 277.
[ bib ]
|
[BMPR07]
|
E. K. Burke, J. Mareček, A. J. Parkes, H. Rudová
(2007).
On a Clique-Based Integer Programming Formulation of Vertex
Colouring with Applications in Course Timetabling.
Tech. Rep. NOTTCS-TR-2007-10, The University of Nottingham,
Nottingham.
[ bib |
http ]
|
[GHO07]
|
M. Gamache, A. Hertz, J. O. Ouellet (2007).
A graph coloring model for a feasibility problem in monthly
crew scheduling with preferential bidding.
Computers & Operations Research, vol. 34, no. 8, pp.
2384-2395.
[ bib |
DOI ]
|
[SRH04]
|
M. D. Smith, N. Ramsey, G. Holloway (2004).
A generalized algorithm for graph-coloring register
allocation.
In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on
Programming language design and implementation, pp. 277-288. ACM Press, New
York, NY, USA.
ISBN 1-58113-807-5.
[ bib |
DOI ]
|
[ZKW03]
|
A. Zymolka, A. M. C. A. Koster, R. Wessäly (2003).
Transparent optical network design with sparse wavelength
conversion.
In Proceedings of the 7th IFIP Working Conference on Optical
Network Design & Modelling, pp. 61-80. Budapest, Hungary.
[ bib ]
|
[BB02]
|
N. Barnier, P. Brisset (2002).
Graph Coloring for Air Traffic Flow Management.
In CPAIOR'02: Fourth International Workshop on Integration of
AI and OR Techniques in Constraint Programming for Combinatorial Optimisation
Problems, pp. 133-147. Le Croisic, France.
[ bib ]
|
[AKL02]
|
M. Allen, G. Kumaran, T. Liu (2002).
A Combined Algorithm for Graph-coloring in Register
Allocation.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 100-111. Ithaca, New York, USA.
[ bib ]
|
[GS02]
|
C. Gomes, D. Shmoys (2002).
Completing Quasigroups or Latin Squares: A Structured Graph
Coloring Problem.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 22-39. Ithaca, New York, USA.
[ bib ]
|
[HS02]
|
S. Hossain, T. Steihaug (2002).
Graph coloring in the estimation of mathematical
derivatives.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 9-16. Ithaca, New York, USA.
[ bib ]
|
[Fre00]
|
R. Freimer (2000).
Generalized map coloring for use in geographical information
systems.
In K.-J. Li, K. Makki, N. Pissinou, S. Ravada (eds.),
ACM-GIS 2000, Proceedings of the Eighth ACM Symposium on Advances in
Geographic Information Systems, pp. 167-173. ACM press, New York, NY, USA.
ISBN 1-58113-319-7.
[ bib |
DOI ]
|
[LC96]
|
G. Lewandowski, A. Condon (1996).
Experiments with parallel graph coloring heuristics and
applications of graph coloring.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 309-334. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[de 85]
|
D. de Werra (1985).
An introduction to timetabling.
European Journal of Operational Research, vol. 19, no. 2, pp.
151-162.
[ bib |
DOI |
http ]
|
[Lei79]
|
F. T. Leighton (1979).
A Graph Coloring Algorithm for Large Scheduling Problems.
Journal of Research of the National Bureau of Standards,
vol. 84, no. 6, pp. 489-506.
[ bib ]
|
[GJS76]
|
M. R. Garey, D. S. Johnson, H. C. So (1976).
An Application of Graph Coloring to Printed Circuit Testing.
IEEE Transactions on Circuits and Systems, vol. 23, pp.
591-599.
[ bib ]
|
[Woo69]
|
D. C. Wood (1969).
A Technique for Coloring a Graph Applicable to Large-Scale
Timetabling Problems.
Computer Journal, vol. 12, pp. 317-322.
[ bib ]
|
[MN08]
|
K. Mizuno, S. Nishihara (2008).
Constructive generation of very hard 3-colorability
instances.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 218-229.
[ bib |
DOI ]
|
[Chv04]
|
V. Chvátal (2004).
Coloring the queen graphs.
Web repository (last visited July 2005).
[ bib |
.html ]
|
[ZKW03]
|
A. Zymolka, A. M. C. A. Koster, R. Wessäly (2003).
Transparent optical network design with sparse wavelength
conversion.
In Proceedings of the 7th IFIP Working Conference on Optical
Network Design & Modelling, pp. 61-80. Budapest, Hungary.
[ bib ]
|
[GS02]
|
C. Gomes, D. Shmoys (2002).
Completing Quasigroups or Latin Squares: A Structured Graph
Coloring Problem.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 22-39. Ithaca, New York, USA.
[ bib ]
|
[HS02]
|
S. Hossain, T. Steihaug (2002).
Graph coloring in the estimation of mathematical
derivatives.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 9-16. Ithaca, New York, USA.
[ bib ]
|
[MN02]
|
K. Mizuno, S. Nishihara (2002).
Toward Ordered Generation of Exceptionally Hard Instances for
Graph 3-Colorability.
In D. S. Johnson, A. Mehrotra, M. Trick (eds.),
Proceedings of the Computational Symposium on Graph Coloring and its
Generalizations, pp. 1-8. Ithaca, New York, USA.
[ bib ]
|
[CD02b]
|
M. Caramia, P. Dell'Olmo (2002).
K-Insertions graphs: a proposal of a new class of
benchmarks.
Manuscript.
[ bib ]
|
[CD02a]
|
M. Caramia, P. Dell'Olmo (2002).
K-FullIns graphs: a proposal of a new class of benchmarks.
Manuscript.
[ bib ]
|
[LC96]
|
G. Lewandowski, A. Condon (1996).
Experiments with parallel graph coloring heuristics and
applications of graph coloring.
vol. 26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 309-334. American Mathematical Society,
Providence, RI, USA.
[ bib ]
|
[MT96]
|
A. Mehrotra, M. Trick (1996).
A Column Generation Approach for Graph Coloring.
INFORMS Journal On Computing, vol. 8, no. 4, pp. 344-354.
[ bib ]
|
[CBP95]
|
J. Culberson, A. Beacham, D. Papp (1995).
Hiding our Colors.
In Proceedings of the CP'95 Workshop on Studying and Solving
Really Hard Problems, pp. 31-42. Cassis, France.
[ bib |
.html ]
|
[JAMS91]
|
D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon (1991).
Optimization by Simulated Annealing: An Experimental
Evaluation; Part II, Graph Coloring and Number Partitioning.
Operations Research, vol. 39, no. 3, pp. 378-406.
[ bib ]
|
[Lew16]
|
R. Lewis (2016).
A Guide to Graph Colouring: Algorithms and Applications.
Springer, Berlin.
ISBN 978-3-319-25728-0.
[ bib |
DOI ]
|
[MT09]
|
E. Malaguti, P. Toth (2009).
A survey on vertex coloring problems.
International Transactions in Operational Research, pp. 1-34.
[ bib |
DOI ]
|
[JMT08]
|
D. S. Johnson, A. Mehrotra, M. A. Trick (2008).
Special issue on computational methods for graph coloring and
its generalizations.
Discrete Applied Mathematics, vol. 156, no. 2, pp. 145-146.
[ bib |
DOI ]
|
[CDS07]
|
M. Chiarandini, I. Dumitrescu, T. Stützle (2007).
Stochastic Local Search Algorithms for the Graph Colouring
Problem.
In T. F. Gonzalez (ed.), Handbook of
Approximation Algorithms and Metaheuristics, Computer & Information Science
Series, pp. 63.1-63.17. Chapman & Hall/CRC, Boca Raton, FL, USA.
Preliminary version available as Tech. Rep. AIDA-05-03 at
Intellectics Group, Computer Science Department, Darmstadt University of
Technology, Darmstadt, Germany.
[ bib |
.pdf ]
|
[GH06]
|
P. Galinier, A. Hertz (2006).
A survey of local search methods for graph coloring.
Computers & Operations Research, vol. 33, pp. 2547-2562.
[ bib |
DOI ]
|
[JMT02]
|
D. S. Johnson, A. Mehrotra, M. Trick (eds.) (2002).
Proceedings of the Computational Symposium on Graph Coloring
and its Generalizations. Ithaca, New York, USA.
[ bib ]
|
[PMX98]
|
P. Pardalos, T. Mavridou, J. Xue (1998).
The graph coloring problem: A bibliographic survey, vol. 2,
pp. 331-395.
Kluwer Academic Publishers, Boston.
[ bib ]
|
[JT96]
|
D. S. Johnson, M. Trick (eds.) (1996).
Cliques, Coloring, and Satisfiability: Second DIMACS
Implementation Challenge, 1993, vol. 26 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science.
American Mathematical Society, Providence, RI, USA.
[ bib ]
|
|