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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Coll, Pablo Enrique, Marenco, Javier Leonardo, Méndez Díaz, Isabel, Zabala, Paula
Publicado: 2002
Materias:
Facets of polyhedra
Graph coloring
Integer programming
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:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_02545330_v116_n1-4_p79_Coll
record_format dspace
spelling paper:paper_02545330_v116_n1-4_p79_Coll2023-06-08T15:21:58Z Facets of the graph coloring polytope Coll, Pablo Enrique Marenco, Javier Leonardo Méndez Díaz, Isabel Zabala, Paula Facets of polyhedra Graph coloring Integer programming 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. Fil:Coll, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Méndez Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Zabala, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2002 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
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Facets of polyhedra
Graph coloring
Integer programming
spellingShingle Facets of polyhedra
Graph coloring
Integer programming
Coll, Pablo Enrique
Marenco, Javier Leonardo
Méndez Díaz, Isabel
Zabala, Paula
Facets of the graph coloring polytope
topic_facet Facets of polyhedra
Graph coloring
Integer programming
description 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.
author Coll, Pablo Enrique
Marenco, Javier Leonardo
Méndez Díaz, Isabel
Zabala, Paula
author_facet Coll, Pablo Enrique
Marenco, Javier Leonardo
Méndez Díaz, Isabel
Zabala, Paula
author_sort Coll, Pablo Enrique
title Facets of the graph coloring polytope
title_short Facets of the graph coloring polytope
title_full Facets of the graph coloring polytope
title_fullStr Facets of the graph coloring polytope
title_full_unstemmed Facets of the graph coloring polytope
title_sort facets of the graph coloring polytope
publishDate 2002
url 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
work_keys_str_mv AT collpabloenrique facetsofthegraphcoloringpolytope
AT marencojavierleonardo facetsofthegraphcoloringpolytope
AT mendezdiazisabel facetsofthegraphcoloringpolytope
AT zabalapaula facetsofthegraphcoloringpolytope
_version_ 1768543655497302016

Ejemplares similares