A cutting plane algorithm for graph coloring

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

Detalles Bibliográficos
Autores principales:	Méndez Díaz, Isabel, Zabala, Paula
Publicado:	2008
Materias:	Cutting plane algorithms Facets of polyhedra Graph coloring Integer programming Computer programming Graph theory Problem solving Algorithms
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n2_p159_MendezDiaz 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	paper:paper_0166218X_v156_n2_p159_MendezDiaz
record_format	dspace
spelling	paper:paper_0166218X_v156_n2_p159_MendezDiaz2023-06-08T15:15:27Z A cutting plane algorithm for graph coloring Méndez Díaz, Isabel Zabala, Paula 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n2_p159_MendezDiaz 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)
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, Isabel Zabala, Paula 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.
author	Méndez Díaz, Isabel Zabala, Paula
author_facet	Méndez Díaz, Isabel Zabala, Paula
author_sort	Méndez Díaz, Isabel
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	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n2_p159_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n2_p159_MendezDiaz
work_keys_str_mv	AT mendezdiazisabel acuttingplanealgorithmforgraphcoloring AT zabalapaula acuttingplanealgorithmforgraphcoloring AT mendezdiazisabel cuttingplanealgorithmforgraphcoloring AT zabalapaula cuttingplanealgorithmforgraphcoloring
_version_	1768542832929275904

A cutting plane algorithm for graph coloring

Ejemplares similares