Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:An exact algorithm for the edge coloring by total labeling problem
Autor:Borghini, F.; Méndez-Díaz, I.; Zabala, P.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Computación, FCEN, Instituto de Investigación en Ciencias de la Computación (ICC), CONICET-UBA, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Branch-and-Cut; Edge coloring; Graph coloring; Total labeling
Año:2018
DOI: http://dx.doi.org/10.1007/s10479-018-2977-x
Título revista:Annals of Operations Research
Título revista abreviado:Ann. Oper. Res.
ISSN:02545330
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v_n_p_Borghini

Referencias:

  • Aardal, K., van Hoesel, S., Koster, A., Mannino, C., Sassano, A., Models and solution techniques for frequency assignment problems (2007) Annals of Operations Research, 153 (1), pp. 79-129
  • Bača, M., Miller, M., Ryan, J., On irregular total labellings (2007) Discrete Mathematics, 307 (11), pp. 1378-1388
  • Brandt, S., Budajov, K., Rautenbach, D., Stiebitz, M., Edge colouring by total labellings (2010) Discrete Mathematics, 310 (2), pp. 199-205
  • Brelaz, D., New methods to color the vertices of a graph (1979) Communications of the ACM, 22 (4), pp. 251-256
  • Burke, E., Mareček, K., Parkes, A., Rudová, H., A branch-and-cut procedure for the Udine Course Timetabling problem (2012) Annals of Operations Research, 194 (1), pp. 71-87
  • Coll, P., Marenco, J., Méndez Díaz, I., Zabala, P., Facets of the graph coloring polytope (2002) Annals of Operations Research, 116 (1), pp. 79-90
  • Cornaz, D., Furini, F., Malaguti, E., Solving vertex coloring problems as maximum weight stable set problems (2017) Discrete Applied Mathematics, 217, pp. 151-162
  • Grötschel, M., Jünger, M., Reinelt, G., A cutting plane algorithm for the linear ordering problem (1984) Operations research, 32 (6), pp. 1195-1220
  • Grötschel, M., Jünger, M., Reinelt, G., Facets of the linear ordering polytope (1985) Mathematical Programming, 33 (1), pp. 43-60
  • IBM. CPLEX Optimizer for z/OS, , http://pic.dhe.ibm.com/infocenter/cplexzos/v12r6/index.jsp
  • Jensen, T., Toth, P., (1995) Graph coloring problems, , Wiley, Hoboken
  • Khennoufa, R., Seba, H., Kheddouci, H., Edge coloring total k-labelling of generalized petersen graphs (2013) Information Processing Letters, 113 (13), pp. 489-494
  • Lee, J., Leung, J., A comparison of two edge-coloring formulations (1993) Operations Research Letters, 13 (4), pp. 215-223
  • Malaguti, E., Méndez-Díaz, I., Miranda-Bront, J., Zabala, P., A branch-and-price algorithm for the (k; c)-coloring problem (2015) Networks, 65 (4), pp. 353-366
  • Misra, J., Gries, D., A constructive proof of vizing’s theorem (1992) Information Processing Letters, 41 (3), pp. 131-133
  • Seba, H., Khennoufa, R., Edge coloring by total labellings of 4-regular circulant graphs (2013) Electronic Notes in Discrete Mathematics, 41, pp. 141-148

Citas:

---------- APA ----------
Borghini, F., Méndez-Díaz, I. & Zabala, P. (2018) . An exact algorithm for the edge coloring by total labeling problem. Annals of Operations Research.
http://dx.doi.org/10.1007/s10479-018-2977-x
---------- CHICAGO ----------
Borghini, F., Méndez-Díaz, I., Zabala, P. "An exact algorithm for the edge coloring by total labeling problem" . Annals of Operations Research (2018).
http://dx.doi.org/10.1007/s10479-018-2977-x
---------- MLA ----------
Borghini, F., Méndez-Díaz, I., Zabala, P. "An exact algorithm for the edge coloring by total labeling problem" . Annals of Operations Research, 2018.
http://dx.doi.org/10.1007/s10479-018-2977-x
---------- VANCOUVER ----------
Borghini, F., Méndez-Díaz, I., Zabala, P. An exact algorithm for the edge coloring by total labeling problem. Ann. Oper. Res. 2018.
http://dx.doi.org/10.1007/s10479-018-2977-x