A large neighborhood search heuristic for graph coloring

Trick, M.A.;Yildiz, H.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Trick, M.A.
    Author
  • Yildiz, H.
    Author
Abstract
We propose a new local search heuristic for graph coloring that searches very large neighborhoods. The heuristic is based on solving a max-cut problem at each step, while the max-cut problem is formally hard, fast heuristics that give "good" cuts are available to solve this. We provide computational results on benchmark instances. The proposed approach is based on similar heuristics used in computer vision.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Trick, M. A., & Yildiz, H. (2007). A large neighborhood search heuristic for graph coloring. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 346-360). Springer-verlag. https://hdl.handle.net/2078.5/221579