The Maximum Clique and Vertex Coloring Chapter uri icon

abstract

  • © Springer International Publishing AG, part of Springer Nature 2018. All rights reserved. In this chapter we review heuristic approaches for two classical and closely related problems of finding a maximum clique and an optimal vertex coloring. Both problems have a wide variety of practical applications, and due to their computational intractability, a significant effort has been focused on developing heuristic methods. This chapter discusses construction heuristics, local search strategies, and metaheuristics designed and/or adapted for the maximum clique and vertex coloring problems.

author list (cited authors)

  • Yezerska, O., & Butenko, S.

citation count

  • 0

Book Title

  • Handbook of Heuristics

publication date

  • August 2018