A polyhedral approach for the equitable coloring problem

In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence that shows t...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Méndez Díaz, Isabel, Severin, Daniel E.
Publicado: 2014
Materias:
Cut and branch
Equitable graph coloring
Integer programming
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v164_nPART2_p413_MendezDiaz
http://hdl.handle.net/20.500.12110/paper_0166218X_v164_nPART2_p413_MendezDiaz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0166218X_v164_nPART2_p413_MendezDiaz
record_format dspace
spelling paper:paper_0166218X_v164_nPART2_p413_MendezDiaz2023-06-08T15:15:33Z A polyhedral approach for the equitable coloring problem Méndez Díaz, Isabel Severin, Daniel E. Cut and branch Equitable graph coloring Integer programming In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence that shows the efficacy of these inequalities used in a cutting-plane algorithm. © 2013 Elsevier B.V. All rights reserved. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Severín, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v164_nPART2_p413_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v164_nPART2_p413_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 Cut and branch
Equitable graph coloring
Integer programming
spellingShingle Cut and branch
Equitable graph coloring
Integer programming
Méndez Díaz, Isabel
Severin, Daniel E.
A polyhedral approach for the equitable coloring problem
topic_facet Cut and branch
Equitable graph coloring
Integer programming
description In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence that shows the efficacy of these inequalities used in a cutting-plane algorithm. © 2013 Elsevier B.V. All rights reserved.
author Méndez Díaz, Isabel
Severin, Daniel E.
author_facet Méndez Díaz, Isabel
Severin, Daniel E.
author_sort Méndez Díaz, Isabel
title A polyhedral approach for the equitable coloring problem
title_short A polyhedral approach for the equitable coloring problem
title_full A polyhedral approach for the equitable coloring problem
title_fullStr A polyhedral approach for the equitable coloring problem
title_full_unstemmed A polyhedral approach for the equitable coloring problem
title_sort polyhedral approach for the equitable coloring problem
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v164_nPART2_p413_MendezDiaz
http://hdl.handle.net/20.500.12110/paper_0166218X_v164_nPART2_p413_MendezDiaz
work_keys_str_mv AT mendezdiazisabel apolyhedralapproachfortheequitablecoloringproblem
AT severindaniele apolyhedralapproachfortheequitablecoloringproblem
AT mendezdiazisabel polyhedralapproachfortheequitablecoloringproblem
AT severindaniele polyhedralapproachfortheequitablecoloringproblem
_version_ 1768546624309559296

Ejemplares similares