zbMATH — the first resource for mathematics

An exact algorithm for the edge coloring by total labeling problem. (English) Zbl 1439.05080
Summary: 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.
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C10 Integer programming
90B18 Communication networks in operations research
90B50 Management decision making, including multiple objectives
90C59 Approximation methods and heuristics in mathematical programming
90C30 Nonlinear programming
Full Text: DOI
[1] Aardal, K.; Van Hoesel, S.; Koster, A.; Mannino, C.; Sassano, A., Models and solution techniques for frequency assignment problems, Annals of Operations Research, 153, 1, 79-129 (2007) · Zbl 1157.90005
[2] Bača, M.; Miller, M.; Ryan, J., On irregular total labellings, Discrete Mathematics, 307, 11, 1378-1388 (2007) · Zbl 1115.05079
[3] Brandt, S.; Budajov, K.; Rautenbach, D.; Stiebitz, M., Edge colouring by total labellings, Discrete Mathematics, 310, 2, 199-205 (2010) · Zbl 1283.05082
[4] Brelaz, D., New methods to color the vertices of a graph, Communications of the ACM, 22, 4, 251-256 (1979) · Zbl 0394.05022
[5] Burke, E.; Mareček, K.; Parkes, A.; Rudová, H., A branch-and-cut procedure for the Udine Course Timetabling problem, Annals of Operations Research, 194, 1, 71-87 (2012) · Zbl 1251.90276
[6] Coll, P.; Marenco, J.; Méndez Díaz, I.; Zabala, P., Facets of the graph coloring polytope, Annals of Operations Research, 116, 1, 79-90 (2002) · Zbl 1013.90097
[7] Cornaz, D.; Furini, F.; Malaguti, E., Solving vertex coloring problems as maximum weight stable set problems, Discrete Applied Mathematics, 217, 151-162 (2017) · Zbl 1358.05098
[8] Grötschel, M.; Jünger, M.; Reinelt, G., A cutting plane algorithm for the linear ordering problem, Operations research, 32, 6, 1195-1220 (1984) · Zbl 0554.90077
[9] Grötschel, M.; Jünger, M.; Reinelt, G., Facets of the linear ordering polytope, Mathematical Programming, 33, 1, 43-60 (1985) · Zbl 0577.05035
[10] IBM. CPLEX Optimizer for z/OS. http://pic.dhe.ibm.com/infocenter/cplexzos/v12r6/index.jsp.
[11] Jensen, T.; Toth, P., Graph coloring problems (1995), Hoboken: Wiley, Hoboken
[12] Khennoufa, R.; Seba, H.; Kheddouci, H., Edge coloring total k-labelling of generalized petersen graphs, Information Processing Letters, 113, 13, 489-494 (2013) · Zbl 1294.05137
[13] Lee, J.; Leung, J., A comparison of two edge-coloring formulations, Operations Research Letters, 13, 4, 215-223 (1993) · Zbl 0783.05049
[14] Malaguti, E.; Méndez-Díaz, I.; Miranda-Bront, J.; Zabala, P., A branch-and-price algorithm for the (k; c)-coloring problem, Networks, 65, 4, 353-366 (2015) · Zbl 1388.05070
[15] Misra, J.; Gries, D., A constructive proof of vizing’s theorem, Information Processing Letters, 41, 3, 131-133 (1992) · Zbl 0795.68157
[16] Seba, H.; Khennoufa, R., Edge coloring by total labellings of 4-regular circulant graphs, Electronic Notes in Discrete Mathematics, 41, 141-148 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.