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, P., Marenco, J., Méndez Díaz, I., Zabala, P.
Formato:	JOUR
Materias:	Facets of polyhedra Graph coloring Integer programming
Acceso en línea:	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	todo:paper_02545330_v116_n1-4_p79_Coll
record_format	dspace
spelling	todo:paper_02545330_v116_n1-4_p79_Coll2023-10-03T15:11:32Z Facets of the graph coloring polytope Coll, P. Marenco, J. Méndez Díaz, I. Zabala, P. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, P. Marenco, J. Méndez Díaz, I. Zabala, P. 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.
format	JOUR
author	Coll, P. Marenco, J. Méndez Díaz, I. Zabala, P.
author_facet	Coll, P. Marenco, J. Méndez Díaz, I. Zabala, P.
author_sort	Coll, P.
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
url	http://hdl.handle.net/20.500.12110/paper_02545330_v116_n1-4_p79_Coll
work_keys_str_mv	AT collp facetsofthegraphcoloringpolytope AT marencoj facetsofthegraphcoloringpolytope AT mendezdiazi facetsofthegraphcoloringpolytope AT zabalap facetsofthegraphcoloringpolytope
_version_	1807321349379588096

Facets of the graph coloring polytope

Ejemplares similares