IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v151y2003i2p379-388.html
   My bibliography  Save this article

A variable neighborhood search for graph coloring

Author

Listed:
  • Avanthay, Cedric
  • Hertz, Alain
  • Zufferey, Nicolas

Abstract

No abstract is available for this item.

Suggested Citation

  • Avanthay, Cedric & Hertz, Alain & Zufferey, Nicolas, 2003. "A variable neighborhood search for graph coloring," European Journal of Operational Research, Elsevier, vol. 151(2), pages 379-388, December.
    • Handle: RePEc:eee:ejores:v:151:y:2003:i:2:p:379-388
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(02)00832-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. David S. Johnson & Cecilia R. Aragon & Lyle A. McGeoch & Catherine Schevon, 1991. "Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning," Operations Research, INFORMS, vol. 39(3), pages 378-406, June.
    2. Chams, M. & Hertz, A. & de Werra, D., 1987. "Some experiments with simulated annealing for coloring graphs," European Journal of Operational Research, Elsevier, vol. 32(2), pages 260-266, November.
    3. J. Randall Brown, 1972. "Chromatic Scheduling and the Chromatic Number Problem," Management Science, INFORMS, vol. 19(4-Part-1), pages 456-463, December.
    4. Philippe Galinier & Jin-Kao Hao, 1999. "Hybrid Evolutionary Algorithms for Graph Coloring," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 379-397, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Iztok Fister & Marjan Mernik & Bogdan Filipič, 2013. "Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm," Computational Optimization and Applications, Springer, vol. 54(3), pages 741-770, April.
    2. HERREMANS, Dorien & WEISSER, Stéphanie & SÖRENSEN, Kenneth & CONKLIN, Darrell, 2014. "Generating structured music using quality metrics based on Markov models," Working Papers 2014019, University of Antwerp, Faculty of Business and Economics.
    3. Severino F. Galán, 2017. "Simple decentralized graph coloring," Computational Optimization and Applications, Springer, vol. 66(1), pages 163-185, January.
    4. Shahram Shahinpour & Sergiy Butenko, 2013. "Algorithms for the maximum k-club problem in graphs," Journal of Combinatorial Optimization, Springer, vol. 26(3), pages 520-554, October.
    5. Casado, Silvia & Laguna, Manuel & Pacheco, Joaquín & Puche, Julio C., 2020. "Grouping products for the optimization of production processes: A case in the steel manufacturing industry," European Journal of Operational Research, Elsevier, vol. 286(1), pages 190-202.
    6. HERREMANS, Dorien & SÖRENSEN, Kenneth, 2012. "Composing Fifth Species Counterpoint Music With Variable Neighborhood Search," Working Papers 2012020, University of Antwerp, Faculty of Business and Economics.
    7. Lü, Zhipeng & Hao, Jin-Kao, 2010. "A memetic algorithm for graph coloring," European Journal of Operational Research, Elsevier, vol. 203(1), pages 241-250, May.
    8. Liang, Yun-Chia & Chen, Yi-Ching, 2007. "Redundancy allocation of series-parallel systems using a variable neighborhood search algorithm," Reliability Engineering and System Safety, Elsevier, vol. 92(3), pages 323-331.
    9. Ayob, Masri & Kendall, Graham, 2008. "A survey of surface mount device placement machine optimisation: Machine classification," European Journal of Operational Research, Elsevier, vol. 186(3), pages 893-914, May.
    10. GARROI, Jean-Jacques & GOOS, Peter & SÖRENSEN, Kenneth, 2006. "A variable-neighbourhood search algorithm for finding optimal run orders in the presence of serial correlation and time trends," Working Papers 2006026, University of Antwerp, Faculty of Business and Economics.
    11. Mabrouk, Bchira Ben & Hasni, Hamadi & Mahjoub, Zaher, 2009. "On a parallel genetic-tabu search based algorithm for solving the graph colouring problem," European Journal of Operational Research, Elsevier, vol. 197(3), pages 1192-1201, September.
    12. Renatha Capua & Yuri Frota & Luiz Satoru Ochi & Thibaut Vidal, 2018. "A study on exponential-size neighborhoods for the bin packing problem with conflicts," Journal of Heuristics, Springer, vol. 24(4), pages 667-695, August.
    13. SYAFITRI, Utami & SARTONO, Bagus & GOOS, Peter, 2015. "D- and I-optimal design of mixture experiments in the presence of ingredient availability constraints," Working Papers 2015003, University of Antwerp, Faculty of Business and Economics.
    14. VÁZQUEZ-ALCOCER, Alan & GOOS, Peter & SCHOEN, Eric D., 2016. "Two-level designs constructed by concatenating orthogonal arrays of strenght three," Working Papers 2016011, University of Antwerp, Faculty of Business and Economics.
    15. H-Y Lin & C-J Liao & C-T Tseng, 2011. "An application of variable neighbourhood search to hospital call scheduling of infant formula promotion," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 949-959, June.
    16. Muñoz, Susana & Teresa Ortuño, M. & Ramírez, Javier & Yáñez, Javier, 2005. "Coloring fuzzy graphs," Omega, Elsevier, vol. 33(3), pages 211-221, June.
    17. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    18. Melo, Rafael A. & Queiroz, Michell F. & Santos, Marcio C., 2021. "A matheuristic approach for the b-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic," European Journal of Operational Research, Elsevier, vol. 295(1), pages 66-81.
    19. HERREMANS, Dorien & SÖRENSEN, Kenneth, 2013. "FuX, an android app that generates counterpoint," Working Papers 2013003, University of Antwerp, Faculty of Business and Economics.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Caramia, Massimiliano & Dell'Olmo, Paolo, 2008. "Embedding a novel objective function in a two-phased local search for robust vertex coloring," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1358-1380, September.
    2. Iztok Fister & Marjan Mernik & Bogdan Filipič, 2013. "Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm," Computational Optimization and Applications, Springer, vol. 54(3), pages 741-770, April.
    3. Severino F. Galán, 2017. "Simple decentralized graph coloring," Computational Optimization and Applications, Springer, vol. 66(1), pages 163-185, January.
    4. M Plumettaz & D Schindl & N Zufferey, 2010. "Ant Local Search and its efficient adaptation to graph colouring," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 819-826, May.
    5. Nicolas Zufferey & Olivier Labarthe & David Schindl, 2012. "Heuristics for a project management problem with incompatibility and assignment costs," Computational Optimization and Applications, Springer, vol. 51(3), pages 1231-1252, April.
    6. Lü, Zhipeng & Hao, Jin-Kao, 2010. "A memetic algorithm for graph coloring," European Journal of Operational Research, Elsevier, vol. 203(1), pages 241-250, May.
    7. Xiao-Feng Xie & Jiming Liu, 2009. "Graph coloring by multiagent fusion search," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 99-123, August.
    8. Pirlot, Marc, 1996. "General local search methods," European Journal of Operational Research, Elsevier, vol. 92(3), pages 493-511, August.
    9. Massimiliano Caramia & Paolo Dell'Olmo, 2001. "Iterative coloring extension of a maximum clique," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(6), pages 518-550, September.
    10. C A Glass & A Prügel-Bennett, 2005. "A polynomially searchable exponential neighbourhood for graph colouring," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 324-330, March.
    11. Valmir C. Barbosa & Carlos A.G. Assis & Josina O. Do Nascimento, 2004. "Two Novel Evolutionary Formulations of the Graph Coloring Problem," Journal of Combinatorial Optimization, Springer, vol. 8(1), pages 41-63, March.
    12. Bradley Hardy & Rhyd Lewis & Jonathan Thompson, 2018. "Tackling the edge dynamic graph colouring problem with and without future adjacency information," Journal of Heuristics, Springer, vol. 24(3), pages 321-343, June.
    13. B Suman & P Kumar, 2006. "A survey of simulated annealing as a tool for single and multiobjective optimization," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(10), pages 1143-1160, October.
    14. Vincenzo Cutello & Giuseppe Nicosia & Mario Pavone, 2007. "An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem," Journal of Combinatorial Optimization, Springer, vol. 14(1), pages 9-33, July.
    15. Celia A. Glass & Adam Prügel-Bennett, 2003. "Genetic Algorithm for Graph Coloring: Exploration of Galinier and Hao's Algorithm," Journal of Combinatorial Optimization, Springer, vol. 7(3), pages 229-236, September.
    16. Olawale Titiloye & Alan Crispin, 2012. "Parameter Tuning Patterns for Random Graph Coloring with Quantum Annealing," PLOS ONE, Public Library of Science, vol. 7(11), pages 1-9, November.
    17. Philippe Galinier & Jin-Kao Hao, 1999. "Hybrid Evolutionary Algorithms for Graph Coloring," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 379-397, December.
    18. Philippe Galinier & Zied Boujbel & Michael Coutinho Fernandes, 2011. "An efficient memetic algorithm for the graph partitioning problem," Annals of Operations Research, Springer, vol. 191(1), pages 1-22, November.
    19. Mabrouk, Bchira Ben & Hasni, Hamadi & Mahjoub, Zaher, 2009. "On a parallel genetic-tabu search based algorithm for solving the graph colouring problem," European Journal of Operational Research, Elsevier, vol. 197(3), pages 1192-1201, September.
    20. Laurent Moalic & Alexandre Gondran, 2018. "Variations on memetic algorithms for graph coloring problems," Journal of Heuristics, Springer, vol. 24(1), pages 1-24, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:151:y:2003:i:2:p:379-388. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.