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

Detalles Bibliográficos
Publicado: 2018
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v_n_p_Koch
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 paper:paper_15725286_v_n_p_Koch
record_format dspace
spelling paper:paper_15725286_v_n_p_Koch2023-06-08T16:24:40Z An integer programming approach to b-coloring 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. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v_n_p_Koch 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
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.
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
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v_n_p_Koch
http://hdl.handle.net/20.500.12110/paper_15725286_v_n_p_Koch
_version_ 1768543250039177216

Ejemplares similares