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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | INPR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_02545330_v_n_p_Borghini |
| Aporte de: |
| id |
todo:paper_02545330_v_n_p_Borghini |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_02545330_v_n_p_Borghini2023-10-03T15:11:36Z An exact algorithm for the edge coloring by total labeling problem Borghini, F. Méndez-Díaz, I. Zabala, P. 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. INPR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Borghini, F. Méndez-Díaz, I. Zabala, P. 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. |
| format |
INPR |
| author |
Borghini, F. Méndez-Díaz, I. Zabala, P. |
| author_facet |
Borghini, F. Méndez-Díaz, I. Zabala, P. |
| author_sort |
Borghini, F. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_02545330_v_n_p_Borghini |
| work_keys_str_mv |
AT borghinif anexactalgorithmfortheedgecoloringbytotallabelingproblem AT mendezdiazi anexactalgorithmfortheedgecoloringbytotallabelingproblem AT zabalap anexactalgorithmfortheedgecoloringbytotallabelingproblem AT borghinif exactalgorithmfortheedgecoloringbytotallabelingproblem AT mendezdiazi exactalgorithmfortheedgecoloringbytotallabelingproblem AT zabalap exactalgorithmfortheedgecoloringbytotallabelingproblem |
| _version_ |
1807319580424536064 |