Facets of the Graph Coloring Polytope |
| |
| Authors: | Pablo Coll Javier Marenco Isabel Méndez Díaz Paula Zabala |
| |
| Institution: | (1) Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, C1428BGA Buenos Aires, Argentina |
| |
| Abstract: | In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem. |
| |
| Keywords: | graph coloring integer programming facets of polyhedra |
| 本文献已被 SpringerLink 等数据库收录！ |
