[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 ]
|