An exact algorithm for the edge coloring by total labeling problem

This paper addresses the edge coloring by total labeling graph problem. This is a labeling of the vertices and edges of a graph such that the weights (colors) of the edges, defined by the sum of its label and the labels of its two endpoints, determine a proper edge coloring of the graph. We propose...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2018
Materias:
Branch-and-Cut
Edge coloring
Graph coloring
Total labeling
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v_n_p_Borghini
http://hdl.handle.net/20.500.12110/paper_02545330_v_n_p_Borghini
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_02545330_v_n_p_Borghini
record_format dspace
spelling paper:paper_02545330_v_n_p_Borghini2023-06-08T15:22:02Z An exact algorithm for the edge coloring by total labeling problem Branch-and-Cut Edge coloring Graph coloring Total labeling This paper addresses the edge coloring by total labeling graph problem. This is a labeling of the vertices and edges of a graph such that the weights (colors) of the edges, defined by the sum of its label and the labels of its two endpoints, determine a proper edge coloring of the graph. We propose two integer programming formulations and derive valid inequalities which are added as cutting planes on a Branch-and-Cut framework. In order to improve the efficiency of the algorithm, we also develop initial and primal heuristics. The algorithm is tested on random instances and the computational results show that it is very effective in comparison with CPLEX. It is displayed that it reduces both the CPU time (for solved instances) and the final percentage gap (for unsolved instances), and that it is capable of solving instances that are out of the reach of CPLEX. © 2018, Springer Science+Business Media, LLC, part of Springer Nature. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v_n_p_Borghini http://hdl.handle.net/20.500.12110/paper_02545330_v_n_p_Borghini
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Branch-and-Cut
Edge coloring
Graph coloring
Total labeling
spellingShingle Branch-and-Cut
Edge coloring
Graph coloring
Total labeling
An exact algorithm for the edge coloring by total labeling problem
topic_facet Branch-and-Cut
Edge coloring
Graph coloring
Total labeling
description This paper addresses the edge coloring by total labeling graph problem. This is a labeling of the vertices and edges of a graph such that the weights (colors) of the edges, defined by the sum of its label and the labels of its two endpoints, determine a proper edge coloring of the graph. We propose two integer programming formulations and derive valid inequalities which are added as cutting planes on a Branch-and-Cut framework. In order to improve the efficiency of the algorithm, we also develop initial and primal heuristics. The algorithm is tested on random instances and the computational results show that it is very effective in comparison with CPLEX. It is displayed that it reduces both the CPU time (for solved instances) and the final percentage gap (for unsolved instances), and that it is capable of solving instances that are out of the reach of CPLEX. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
title An exact algorithm for the edge coloring by total labeling problem
title_short An exact algorithm for the edge coloring by total labeling problem
title_full An exact algorithm for the edge coloring by total labeling problem
title_fullStr An exact algorithm for the edge coloring by total labeling problem
title_full_unstemmed An exact algorithm for the edge coloring by total labeling problem
title_sort exact algorithm for the edge coloring by total labeling problem
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v_n_p_Borghini
http://hdl.handle.net/20.500.12110/paper_02545330_v_n_p_Borghini
_version_ 1768543081291841536

Ejemplares similares