A cutting plane algorithm for graph coloring |
| |
| Authors: | Isabel Mé ndez-Dí az |
| |
| Affiliation: | Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina |
| |
| Abstract: | We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm. |
| |
| Keywords: | Graph coloring Integer programming Facets of polyhedra Cutting plane algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
