A cutting plane algorithm for graph coloring

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Méndez-Díaz, I., Zabala, P.
Formato:	Artículo publishedVersion
Lenguaje:	Inglés
Publicado:	2008
Materias:	Cutting plane algorithms Facets of polyhedra Graph coloring Integer programming Computer programming Graph theory Problem solving Algorithms
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n2_p159_MendezDiaz
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paperaa:paper_0166218X_v156_n2_p159_MendezDiaz
record_format	dspace
spelling	paperaa:paper_0166218X_v156_n2_p159_MendezDiaz2023-06-12T16:46:52Z A cutting plane algorithm for graph coloring Discrete Appl Math 2008;156(2):159-179 Méndez-Díaz, I. Zabala, P. Cutting plane algorithms Facets of polyhedra Graph coloring Integer programming Computer programming Graph theory Integer programming Problem solving Cutting plane algorithms Facets of polyhedra Graph coloring Algorithms 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. © 2007 Elsevier B.V. All rights reserved. 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. 2008 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n2_p159_MendezDiaz
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language	Inglés
orig_language_str_mv	eng
topic	Cutting plane algorithms Facets of polyhedra Graph coloring Integer programming Computer programming Graph theory Integer programming Problem solving Cutting plane algorithms Facets of polyhedra Graph coloring Algorithms
spellingShingle	Cutting plane algorithms Facets of polyhedra Graph coloring Integer programming Computer programming Graph theory Integer programming Problem solving Cutting plane algorithms Facets of polyhedra Graph coloring Algorithms Méndez-Díaz, I. Zabala, P. A cutting plane algorithm for graph coloring
topic_facet	Cutting plane algorithms Facets of polyhedra Graph coloring Integer programming Computer programming Graph theory Integer programming Problem solving Cutting plane algorithms Facets of polyhedra Graph coloring Algorithms
description	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. © 2007 Elsevier B.V. All rights reserved.
format	Artículo Artículo publishedVersion
author	Méndez-Díaz, I. Zabala, P.
author_facet	Méndez-Díaz, I. Zabala, P.
author_sort	Méndez-Díaz, I.
title	A cutting plane algorithm for graph coloring
title_short	A cutting plane algorithm for graph coloring
title_full	A cutting plane algorithm for graph coloring
title_fullStr	A cutting plane algorithm for graph coloring
title_full_unstemmed	A cutting plane algorithm for graph coloring
title_sort	cutting plane algorithm for graph coloring
publishDate	2008
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n2_p159_MendezDiaz
work_keys_str_mv	AT mendezdiazi acuttingplanealgorithmforgraphcoloring AT zabalap acuttingplanealgorithmforgraphcoloring AT mendezdiazi cuttingplanealgorithmforgraphcoloring AT zabalap cuttingplanealgorithmforgraphcoloring
_version_	1769810113294499840

A cutting plane algorithm for graph coloring

Ejemplares similares