An integer programming approach to b-coloring

In the b-coloring problem, we aim to assign colors from a set C to the vertices of a graph G in such a way that adjacent vertices do not receive the same color, and for every c∈C we have a c-colored vertex v in G such that every color in C∖{c} is assigned to at least one of v's neighbors. It ha...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Koch, I., Marenco, J.
Formato: INPR
Materias:
b-coloring
Cutting planes
Facets
Integer programming
Color
Graph theory
Adjacent vertices
Branch and cut
Coloring problems
Integer programming formulations
NP Complete
Valid inequality
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15725286_v_n_p_Koch
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_15725286_v_n_p_Koch
record_format dspace
spelling todo:paper_15725286_v_n_p_Koch2023-10-03T16:27:21Z An integer programming approach to b-coloring Koch, I. Marenco, J. b-coloring Cutting planes Facets Integer programming Color Graph theory Adjacent vertices Branch and cut Coloring problems Cutting planes Facets Integer programming formulations NP Complete Valid inequality Integer programming In the b-coloring problem, we aim to assign colors from a set C to the vertices of a graph G in such a way that adjacent vertices do not receive the same color, and for every c∈C we have a c-colored vertex v in G such that every color in C∖{c} is assigned to at least one of v's neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. © 2018 Elsevier B.V. INPR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15725286_v_n_p_Koch
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic b-coloring
Cutting planes
Facets
Integer programming
Color
Graph theory
Adjacent vertices
Branch and cut
Coloring problems
Cutting planes
Facets
Integer programming formulations
NP Complete
Valid inequality
Integer programming
spellingShingle b-coloring
Cutting planes
Facets
Integer programming
Color
Graph theory
Adjacent vertices
Branch and cut
Coloring problems
Cutting planes
Facets
Integer programming formulations
NP Complete
Valid inequality
Integer programming
Koch, I.
Marenco, J.
An integer programming approach to b-coloring
topic_facet b-coloring
Cutting planes
Facets
Integer programming
Color
Graph theory
Adjacent vertices
Branch and cut
Coloring problems
Cutting planes
Facets
Integer programming formulations
NP Complete
Valid inequality
Integer programming
description In the b-coloring problem, we aim to assign colors from a set C to the vertices of a graph G in such a way that adjacent vertices do not receive the same color, and for every c∈C we have a c-colored vertex v in G such that every color in C∖{c} is assigned to at least one of v's neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. © 2018 Elsevier B.V.
format INPR
author Koch, I.
Marenco, J.
author_facet Koch, I.
Marenco, J.
author_sort Koch, I.
title An integer programming approach to b-coloring
title_short An integer programming approach to b-coloring
title_full An integer programming approach to b-coloring
title_fullStr An integer programming approach to b-coloring
title_full_unstemmed An integer programming approach to b-coloring
title_sort integer programming approach to b-coloring
url http://hdl.handle.net/20.500.12110/paper_15725286_v_n_p_Koch
work_keys_str_mv AT kochi anintegerprogrammingapproachtobcoloring
AT marencoj anintegerprogrammingapproachtobcoloring
AT kochi integerprogrammingapproachtobcoloring
AT marencoj integerprogrammingapproachtobcoloring
_version_ 1807314675434520576

Ejemplares similares