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:	JOUR
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	todo:paper_0166218X_v156_n2_p159_MendezDiaz
record_format	dspace
spelling	todo:paper_0166218X_v156_n2_p159_MendezDiaz2023-10-03T15:03:35Z A cutting plane algorithm for graph coloring 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. JOUR 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)
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	JOUR
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
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_	1807323708006596608

A cutting plane algorithm for graph coloring

Ejemplares similares