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, Isabel, Zabala, Paula
Publicado: 2000
Materias:
Facets of Polyhedra
Graph Coloring
Integer Programming
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz
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 paper:paper_15710653_v7_n_p178_MendezDiaz
record_format dspace
spelling paper:paper_15710653_v7_n_p178_MendezDiaz2023-06-08T16:24:31Z A polyhedral approach for graph coloring Méndez Díaz, Isabel Zabala, Paula 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. 2000 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz 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, Isabel
Zabala, Paula
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.
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 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
publishDate 2000
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz
http://hdl.handle.net/20.500.12110/paper_15710653_v7_n_p178_MendezDiaz
work_keys_str_mv AT mendezdiazisabel apolyhedralapproachforgraphcoloring
AT zabalapaula apolyhedralapproachforgraphcoloring
AT mendezdiazisabel polyhedralapproachforgraphcoloring
AT zabalapaula polyhedralapproachforgraphcoloring
_version_ 1768543532442714112

Ejemplares similares