simplemeta.bib
@comment{{This file has been generated by bib2bib 1.95}}
@comment{{Command line: /usr/bin/bib2bib --expand -ob simplemeta.bib -oc simplemeta-list.bib ../all-entries.bib ./bib-gualandi.bib -c 'keywords : "graph coloring problem"' -c 'keywords : "simple metaheuristics"'}}
@inproceedings{Allen02,
author = {M. Allen and G. Kumaran and T. Liu},
title = {A Combined Algorithm for Graph-coloring in Register Allocation},
pages = {100--111},
crossref = {symposium02},
keywords = {graph coloring problem, local search methods, simple metaheuristics,
applications}
}
@inproceedings{CutNicPav03,
author = {Vincenzo Cutello and Giuseppe Nicosia and Mario Pavone},
title = {A Hybrid Immune Algorithm with Information Gain for the Graph Coloring
Problem},
pages = {171--182},
crossref = {gecco2003:p},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@inproceedings{PhaSki02,
author = {Vinhthuy Phan and Steven Skiena},
title = {Coloring Graphs With a General Heuristic Search Engine},
pages = {92--99},
crossref = {symposium02},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@inproceedings{DBLP:conf/ae/PorumbelHK07,
author = {Daniel Cosmin Porumbel and Jin-Kao Hao and Pascale Kuntz},
title = {A Study of Evaluation Functions for the Graph K-Coloring Problem},
booktitle = {Artificial Evolution},
year = {2007},
pages = {124-135},
bibsource = {DBLP, http://dblp.uni-trier.de},
crossref = {DBLP:conf/ae/2007},
doi = {10.1007/978-3-540-79305-2_11},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@inproceedings{TriYil07,
author = {Michael A. Trick and Hakan Yildiz},
title = {A Large Neighborhood Search Heuristic for Graph Coloring},
year = {2007},
pages = {346-360},
bibsource = {DBLP, http://dblp.uni-trier.de},
crossref = {DBLP:conf/cpaior/2007},
doi = {10.1007/978-3-540-72397-4_25},
keywords = {graph coloring problem, local search methods, simple metaheuristics,
large neighborhoods},
optbooktitle = {CPAIOR}
}
@article{AvaHerZuf03,
author = {C. Avanthay and A. Hertz and N. Zufferey},
title = {A variable neighborhood search for graph coloring},
journal = {European Journal of Operational Research},
year = {2003},
keywords = {graph coloring problem, local search methods, simple metaheuristics},
optpages = {379--388},
optvolume = {151}
}
@article{DiBJagHug03,
author = {Andrea Di Blas and Arun Jagota and Richard Hughey},
title = {A Range-Compaction Heuristic for Graph Coloring},
journal = {Journal of Heuristics},
year = {2003},
volume = {9},
pages = {489--506},
number = {3},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{BloZuf08,
author = {Ivo Bl{\"o}chliger and Nicolas Zufferey},
title = {A graph coloring heuristic using partial solutions and a reactive
tabu scheme},
journal = {Computers \& Operations Research},
year = {2008},
volume = {35},
pages = {960--975},
number = {3},
doi = {doi:10.1016/j.cor.2006.05.014},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{DBLP:journals/dam/CaramiaD08,
author = {Massimiliano Caramia and Paolo Dell'Olmo},
title = {Coloring graphs by iterated local search traversing feasible and
infeasible solutions},
journal = {Discrete Applied Mathematics},
year = {2008},
volume = {156},
pages = {201-217},
number = {2},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1016/j.dam.2006.07.013},
keywords = {graph coloring problem, local search methods, simple metaheuristics,
large neighborhoods}
}
@article{CarDelIta07,
author = {Massimiliano Caramia and Paolo Dell'Olmo and Giuseppe F. Italiano},
title = {CHECKCOL: Improved local search for graph coloringstar},
journal = {Journal of Discrete Algorithms},
year = {2006},
volume = {4},
pages = {277--298},
number = {2},
doi = {doi:10.1016/j.jda.2005.03.006},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@incollection{Chiarandini2008a,
author = {Chiarandini, Marco and Dumitrescu, Irina and St{\"u}tzle, Thomas},
title = {Very Large-Scale Neighborhood Search: Overview and Case Studies on
Coloring Problems},
booktitle = {Hybrid Metaheuristics},
publisher = {Springer},
year = {2008},
editor = {Christian Blum and Maria J. Blesa and Andrea Roli and Michael Sampels},
volume = {114},
series = {Studies in Computational Intelligence},
pages = {117--150},
abstract = {Two key issues in local search algorithms are the definition of a
neighborhood and the way to examine it. In this chapter we consider
techniques for examining very large neighborhoods, in particular,
ways for exactly searching them. We first illustrate such techniques
using three paradigmatic examples. In the largest part of the chapter,
we focus on the development and experimental study of very largescale
neighborhood search algorithms for two coloring problems. The first
example concerns the well-known (vertex) graph coloring problem.
Despite initial promising results on the use of very large-scale
neighborhoods, our final conclusion was negative: the usage of the
proposed very large-scale neighborhoods did not help to improve the
performance of effective stochastic local search algorithms. The
second example, the graph set T-coloring problem, yielded more positive
results. In this case, a very large-scale neighborhood that was specially
tailored for this problem and that can be efficiently searched, resulted
to be an essential component of a new state-of-the-art algorithm
for various instance classes.},
doi = {10.1007/978-3-540-78295-7_5},
keywords = {graph coloring problem, local search methods, simple metaheuristics,
large neighborhoods},
owner = {marco},
timestamp = {2009.03.23}
}
@inproceedings{Chiarandini2010f,
author = {Chiarandini, Marco and St{\"u}tzle, Thomas},
title = {An Analysis of Heuristics for Vertex Colouring},
booktitle = {Experimental Algorithms, Proceedings of the 9th International Symposium,
(SEA 2010)},
year = {2010},
editor = {Paola Festa},
volume = {6049},
series = {Lecture Notes in Computer Science},
pages = {326--337},
month = {May},
publisher = {Springer},
note = {Supplementary material and source code available at \url{http://www.imada.sdu.dk/~marco/gcp-study/}},
abstract = {Several heuristics have been presented in the literature for finding
a proper colouring of the vertices of a graph using the least number
of colours. These heuristics are commonly compared on a set of graphs
that served two DIMACS competitions. This set does not permit the
statistical study of relations between algorithm performance and
structural features of graphs. We generate a new set of random graphs
controlling their structural features and advance the knowledge of
heuristics for graph colouring. We maintain and make all algorithms
described here publically available in order to facilitate future
comparisons.},
doi = {10.1007/978-3-642-13193-6_28},
keywords = {Chiarandini, graph coloring problem, simple metaheuristics, construction
heuristics},
location = {Ischia Island, Naples, Italy, May 2010},
owner = {marco},
timestamp = {2010.07.06}
}
@article{DiBlas2002,
author = {Di Blas, A. and Jagota, A. and Hughey, R.},
title = {Energy function-based approaches to graph coloring},
journal = {Neural Networks, IEEE Transactions on},
year = {2002},
volume = {13},
pages = {81 -91},
number = {1},
month = {jan},
abstract = {We describe an approach to optimization based on a multiple-restart
quasi-Hopfield network where the only problem-specific knowledge
is embedded in the energy function that the algorithm tries to minimize.
We apply this method to three different variants of the graph coloring
problem: the minimum coloring problem, the spanning subgraph k-coloring
problem, and the induced subgraph k-coloring problem. Though Hopfield
networks have been applied in the past to the minimum coloring problem,
our encoding is more natural and compact than almost all previous
ones. In particular, we use k-state neurons while almost all previous
approaches use binary neurons. This reduces the number of connections
in the network from (Nk)2 to N2 asymptotically and also circumvents
a problem in earlier approaches, that of multiple colors being assigned
to a single vertex. Experimental results show that our approach compares
favorably with other algorithms, even nonneural ones specifically
developed for the graph coloring problem},
doi = {10.1109/72.977273},
issn = {1045-9227},
keywords = {graph coloring problem, simple metaheuristics, Hopfield neural networks;energy
minimization;graph coloring;k-state neurons;multiple-restart;optimization;quasi-Hopfield
network;simulated annealing;Hopfield neural nets;graph colouring;optimisation;}
}
@inproceedings{FabHog02,
author = {Alex Fabrikant and Tad Hogg},
title = {Graph Coloring with Quantum Heuristics},
booktitle = {Proceedings of the Eighteenth National Conference on Artificial Intelligence
and Fourteenth Conference on Innovative Applications of Artificial
Intelligence, Edmonton, Alberta, Canada. AAAI Press},
year = {2002},
pages = {22--27},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{GenHerStL07,
author = {Bernard Gendron and Alain Hertz and Patrick St-Louis},
title = {On edge orienting methods for graph coloring},
journal = {Journal of combinatorial optimization},
year = {2007},
volume = {13},
pages = {163--178},
number = {2},
doi = {10.1007/s10878-006-9019-3},
keywords = {graph coloring problem, local search methods, simple metaheuristics,
large neighborhoods}
}
@article{VelLag02,
author = {J.L.~Gonz\'alez-Velarde and M.~Laguna},
title = {Tabu Search with Simple Ejection Chains for Coloring Graphs},
journal = {Annals of Operations Research},
year = {2002},
volume = {117},
pages = {165-174},
number = {1-4},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@inproceedings{HamHao01:ss,
author = {J.-P. Hamiez and J.-K. Hao},
title = {Scatter Search for Graph Coloring},
booktitle = {Artificial Evolution},
year = {2001},
editor = {P. Collet and C. Fonlupt and J.-K. Hao and E. Lutton and M. Schoenauer},
volume = {2310},
series = {Lecture Notes in Computer Science},
pages = {168--179},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@inproceedings{HamHao01:a,
author = {J.-P. Hamiez and J.-K. Hao},
title = {Experimental Investigation of Scatter Search for Graph Coloring},
booktitle = {Proceedings of the Metaheuristics International Conference},
year = {2001},
pages = {311--316},
address = {Porto, Portugal},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{Her91,
author = {A. Hertz},
title = {COSINE: A new graph coloring algorithm},
journal = {Operations Research Letters},
year = {1991},
volume = {10},
pages = {411--415},
number = {7},
doi = {doi:10.1016/0167-6377(91)90043-O},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{HerDeW87,
author = {A.~Hertz and D.~{de Werra}},
title = {Using Tabu Search Techniques for Graph Coloring},
journal = {Computing},
year = {1987},
volume = {39},
pages = {345--351},
number = {4},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{Hertz2008,
author = {A. Hertz and M. Plumettaz and N. Zufferey},
title = {Variable Space Search for Graph Coloring},
journal = {Discrete Applied Mathematics},
year = {2008},
volume = {156},
pages = {2551 -- 2560},
number = {13},
doi = {10.1016/j.dam.2008.11.008},
keywords = {graph coloring problem, simple metaheuristics, local search},
owner = {marco},
timestamp = {2010.08.06}
}
@article{JohAraMcGSch91:or,
author = {D. S. Johnson and C. R. Aragon and L. A. McGeoch and C.~Schevon},
title = {Optimization by Simulated Annealing: An Experimental Evaluation;
Part {II}, Graph Coloring and Number Partitioning},
journal = {Operations Research},
year = {1991},
volume = {39},
pages = {378--406},
number = {3},
file = {:home/marco/Literature/Applications/Coloring/johnson91.pdf:PDF},
keywords = {graph coloring problem, local search methods, simple metaheuristics,
instances}
}
@article{KocGloBahReg05,
author = {Gary A. Kochenberger and Fred Glover and Bahram Alidaee and Cesar
Rego},
title = {An Unconstrained Quadratic Binary Approach to the Vertex Coloring
Problem},
journal = {Annals of Operations Research},
year = {2005},
volume = {139},
pages = {229--241},
number = {1},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{LagMar01,
author = {Manuel Laguna and Rafael Mart\'i},
title = {A {GRASP} for Coloring Sparse Graphs},
journal = {Computational optimization and applications},
year = {2001},
volume = {19},
pages = {165--178},
number = {2},
address = {Norwell, MA, USA},
doi = {10.1023/A:1011237503342},
issn = {0926-6003},
keywords = {graph coloring problem, local search methods, simple metaheuristics},
publisher = {Kluwer Academic Publishers}
}
@article{Lewis2009,
author = {Rhyd Lewis},
title = {A general-purpose hill-climbing method for order independent minimum
gr ouping problems: A case study in graph colouring and bin packing},
journal = {Computers \& Operations Research},
year = {2009},
volume = {36},
pages = {2295 - 2310},
number = {7},
abstract = {A class of problems referred to as order independent minimum grouping
problems i s examined and an intuitive hill-climbing method for solving
such problems is pr oposed. Example applications of this generic
method are made to two well-known p roblems belonging to this class:
graph colouring and bin packing. Using a wide v ariety of different
problem instance-types, these algorithms are compared to two other
generic methods for this problem type: the iterated greedy algorithm
and the grouping genetic algorithm. The results of these comparisons
indicate that t he presented applications of the hill-climbing approach
are able to significantl y outperform these algorithms in many cases.
A number of reasons for these chara cteristics are given in the presented
analyses.},
doi = {10.1016/j.cor.2008.09.004},
issn = {0305-0548},
keywords = {graph coloring problem, simple metaheuristics},
url = {http://www.sciencedirect.com/science/article/B6VC5-4TGHNJ4-1/2/1040b5ca8e f6fc2ddf012f32f3de9cb5}
}
@inproceedings{MorSha90,
author = {C. Morgenstern and H. Shapiro},
title = {Coloration neighborhood structures for general graph coloring},
booktitle = {Proceedings of the first annual {ACM-SIAM} Symposium on Discrete
algorithms},
year = {1990},
pages = {226--235},
publisher = {Society for Industrial and Applied Mathematics, Philadelphia, PA,
USA},
isbn = {0-89871-251-3},
keywords = {graph coloring problem, local search methods, simple metaheuristics},
location = {San Francisco, California, United States}
}
@inproceedings{OnoYagHir07,
author = {T. Ono and M. Yagiura and T. Hirata},
title = {A vector assignment approach for the graph coloring problem},
booktitle = {Proc. Learning and Intelligent OptimizatioN Conference (LION 2007
II)},
year = {2007},
address = {Trento, Italy},
note = {to appear as LNCS},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@phdthesis{Stu98:phd,
author = {T. St{\"u}tzle},
title = {Local Search Algorithms for Combinatorial Problems --- Analysis,
Improvements, and New Applications},
school = {FB Informatik, Technische Universit{\"a}t Darmstadt, Darmstadt, Germany},
year = {1998},
keywords = {graph coloring problem, local search methods, simple metaheuristics}
}
@article{Talavan2008,
author = {Pedro M. Talaván and Javier Yáñez},
title = {The graph coloring problem: A neuronal network approach},
journal = {European Journal of Operational Research},
year = {2008},
volume = {191},
pages = {100 - 111},
number = {1},
doi = {DOI: 10.1016/j.ejor.2007.08.034},
issn = {0377-2217},
keywords = {graph coloring problem, simple metaheuristics, Artificial neural networks},
url = {http://www.sciencedirect.com/science/article/B6VCT-4PKXBRB-2/2/55e3768b11 3eff1004b2a4338461f0b0}
}
@proceedings{gecco2003:p,
title = {Genetic and Evolutionary Computation - GECCO 2003, Genetic and Evolutionary
Computation Conference, Chicago, IL, USA, July 12-16, 2003. Proceedings,
Part I},
year = {2003},
editor = {Erick Cant{\'u}-Paz et al.},
volume = {2723},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag, Berlin, Germany},
bibsource = {DBLP, http://dblp.uni-trier.de},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference
(GECCO-2003)},
isbn = {3-540-40602-6},
location = {Chicago, IL, USA},
opteditor = {and James A. Foster and Kalyanmoy Deb and Lawrence Davis and Rajkumar
Roy and Una-May O'Reilly and Hans-Georg Beyer and Russell K. Standish
and Graham Kendall and Stewart W. Wilson and Mark Harman and Joachim
Wegener and Dipankar Dasgupta and Mitchell A. Potter and Alan C.
Schultz and Kathryn A. Dowsland and Natasa Jonoska and Julian F.
Miller}
}
@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}
}
@proceedings{DBLP:conf/ae/2007,
title = {Artificial Evolution, 8th International Conference, Evolution Artificielle,
EA 2007, Tours, France, October 29-31, 2007, Revised Selected Papers},
year = {2008},
editor = {Nicolas Monmarch{\'e} and El-Ghazali Talbi and Pierre Collet and
Marc Schoenauer and Evelyne Lutton},
volume = {4926},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
bibsource = {DBLP, http://dblp.uni-trier.de},
booktitle = {Artificial Evolution},
isbn = {978-3-540-79304-5}
}
@proceedings{DBLP:conf/cpaior/2007,
year = {2007},
editor = {Pascal {Van Hentenryck} and Laurence A. Wolsey},
volume = {4510},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
bibsource = {DBLP, http://dblp.uni-trier.de},
booktitle = {Integration of AI and OR Techniques in Constraint Programming for
Combinatorial Optimization Problems},
isbn = {978-3-540-72396-7},
optbooktitle = {CPAIOR},
opttitile = {4th International Conference, CPAIOR 2007, Brussels, Belgium, May
23-26, 2007, Proceedings}
}