×

Algorithmic expedients for the \(S\)-labeling problem. (English) Zbl 1458.90626

Summary: Graph labeling problems have been widely studied in the last decades and have a vast area of application. In this work, we study the recently introduced \(S\)-labeling problem, in which the nodes get labeled using labels from 1 to \(|V|\) and for each edge the contribution to the objective function, called \(S\)-labeling number of the graph, is the minimum label of its end-nodes. The goal is to find a labeling with minimum value. The problem is NP-hard for planar subcubic graphs, although for many other graph classes the complexity status is still unknown. In this paper, we present different algorithmic approaches for tackling this problem: we develop an exact solution framework based on mixed-integer programming (MIP) which is enhanced with valid inequalities, starting and primal heuristics and specialized branching rules. We show that our MIP formulation has no integrality gap for paths, cycles and perfect \(n\)-ary trees, and, to the best of our knowledge, we give the first polynomial-time algorithm for the problem on \(n\)-ary trees as well as a closed formula for the \(S\)-labeling number for such trees. Moreover, we also present a Lagrangian heuristic and a constraint programming approach. A computational study is carried out in order to (i) investigate if there may be other special graph classes, where our MIP formulation has no integrality gap, and (ii) assess the effectiveness of the proposed solution approaches for solving the problem on a dataset consisting of general graphs.

MSC:

90C35 Programming involving graphs or networks
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming

Software:

TScb; SAcb; NetworkX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 1, 42-54 (2005) · Zbl 1076.90037
[2] Balakrishnan, A.; Magnanti, T. L.; Wong, R. T., A dual-ascent procedure for large-scale uncapacitated network design, Oper. Res., 37, 5, 716-740 (1989) · Zbl 0681.90083
[3] Black, P. E., Perfect k-ary tree, Dictionary of Algorithms and Data Structures (2018)
[4] Bloom, G. S.; Golomb, S. W., Applications of numbered undirected graphs, Proc. IEEE, 65, 4, 562-570 (1977)
[5] Cho, N.; Linderoth, J., Row-partition branching for set partitioning problems, Proceedings of the INFORMS Computing Society Meeting, 119-133 (2015)
[6] Conforti, M.; Cornuéjols, G.; Zambelli, G., Integer Programming (2014), Springer Berlin · Zbl 1307.90001
[7] Dehghan, A.; Sadeghi, M. R.; Ahadi, A., Algorithmic complexity of proper labeling problems, Theor. Comput. Sci., 495, 25-36 (2013) · Zbl 1295.05203
[8] Díaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM Comput. Surv. (CSUR), 34, 3, 313-356 (2002)
[9] Duarte, A.; Martí, R.; Resende, M. G.C.; Silva, R. M.A., Grasp with path relinking heuristics for the antibandwidth problem, Networks, 58, 3, 171-189 (2011) · Zbl 1229.90095
[10] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Oper. Res., 26, 6, 992-1009 (1978) · Zbl 0422.90053
[11] Fertin, G.; Rusu, I.; Vialette, S., Algorithmic aspects of the S-labeling problem, (Lipták, Z.; Smyth, W. F., International Workshop on Combinatorial Algorithms (2015), Springer), 173-184 · Zbl 1476.68206
[12] Fertin, G.; Rusu, I.; Vialette, S., The S-labeling problem: An algorithmic tour, Discrete Applied Mathematics, 246, 49-61 (2018) · Zbl 1390.05202
[13] Fertin, G.; Vialette, S., On the s-labeling problem, Electron. Note. Discret. Math., 34, 273-277 (2009) · Zbl 1273.05191
[14] Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems, Manag. Sci., 27, 1, 1-18 (1981) · Zbl 0466.90054
[15] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin., 16, 6, 1-219 (2009)
[16] Hagberg, A. A.; Schult, D. A.; Swart, P. J., Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (SciPy2008), 11-15 (2008), Pasadena, CA USA
[17] Heuvel, J. V.d.; Leese, R. A.; Shepherd, M. A., Graph labeling and radio channel assignment, J. Graph Theory, 29, 4, 263-283 (1998) · Zbl 0930.05087
[18] Jin, X. T.; Yeh, R. K., Graph distance-dependent labeling related to code assignment in computer networks, Naval Res. Logist. (NRL), 52, 2, 159-164 (2005) · Zbl 1063.05118
[19] Karp, R. M., Mapping the genome: some combinatorial problems arising in molecular biology, Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, 278-285 (1993), ACM · Zbl 1310.92022
[20] Kuhn, H. W., The hungarian method for the assignment problem, Naval Res. Logist.Q., 2, 1-2, 83-97 (1955) · Zbl 0143.41905
[21] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0652.90067
[22] Rodriguez-Tello, E.; Hao, J. K.; Torres-Jimenez, J., An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem, Comput. Oper. Res., 35, 10, 3331-3346 (2008) · Zbl 1133.90424
[23] Rodriguez-Tello, E.; Romero-Monsivais, H.; Ramirez-Torres, G.; Lardeux, F., Tabu search for the cyclic bandwidth problem, Comput. Oper. Res., 57, 17-32 (2015) · Zbl 1348.90604
[24] Vialette, S., Packing of (0, 1)-matrices, RAIRO-Theor. Inform. Appl., 40, 4, 519-535 (2006) · Zbl 1110.68049
[25] Wolsey, L., Integer Programming (1998), Wiley: Wiley New York · Zbl 0930.90072
[26] Wong, R. T., A dual ascent approach for Steiner tree problems on a directed graph, Math. Programm., 28, 3, 271-287 (1984) · Zbl 0532.90092
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.