A polyhedral approach for graph coloring

We present an approach based on an integer programming formulation of the graph coloring problem. Our goal is to develop a model that removes 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 a...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	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_15710653_v7_n_p178_MendezDiaz
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_15710653_v7_n_p178_MendezDiaz
record_format	dspace
spelling	todo:paper_15710653_v7_n_p178_MendezDiaz2023-10-03T16:27:10Z A polyhedral approach for graph coloring Méndez Díaz, I. Zabala, P. Facets of Polyhedra Graph Coloring Integer Programming We present an approach based on an integer programming formulation of the graph coloring problem. Our goal is to develop a model that removes 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 associated polytope. The theoretical results described here will be used to design an efficient Branch&Cut algorithm in a future work. 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_15710653_v7_n_p178_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	Facets of Polyhedra Graph Coloring Integer Programming
spellingShingle	Facets of Polyhedra Graph Coloring Integer Programming Méndez Díaz, I. Zabala, P. A polyhedral approach for graph coloring
topic_facet	Facets of Polyhedra Graph Coloring Integer Programming
description	We present an approach based on an integer programming formulation of the graph coloring problem. Our goal is to develop a model that removes 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 associated polytope. The theoretical results described here will be used to design an efficient Branch&Cut algorithm in a future work.
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 polyhedral approach for graph coloring
title_short	A polyhedral approach for graph coloring
title_full	A polyhedral approach for graph coloring
title_fullStr	A polyhedral approach for graph coloring
title_full_unstemmed	A polyhedral approach for graph coloring
title_sort	polyhedral approach for graph coloring
url	http://hdl.handle.net/20.500.12110/paper_15710653_v7_n_p178_MendezDiaz
work_keys_str_mv	AT mendezdiazi apolyhedralapproachforgraphcoloring AT zabalap apolyhedralapproachforgraphcoloring AT mendezdiazi polyhedralapproachforgraphcoloring AT zabalap polyhedralapproachforgraphcoloring
_version_	1807315607475978240

A polyhedral approach for graph coloring

Ejemplares similares