Facets of the graph coloring polytope
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 colori...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Publicado: |
2002
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v116_n1-4_p79_Coll http://hdl.handle.net/20.500.12110/paper_02545330_v116_n1-4_p79_Coll |
| Aporte de: |
| Sumario: | 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. |
|---|