×

Fast exact algorithm for \(L(2,1)\)-labeling of graphs. (English) Zbl 1417.05214

Summary: An \(L(2,1)\)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the \(L(2,1)\)-span of a graph is the minimum possible span of its \(L(2,1)\)-labelings. We show how to compute the \(L(2,1)\)-span of a connected graph in time \(O^\ast(2.6488^n)\). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time \(O^\ast(2.5944^n)\) for claw-free graphs, and in time \(O^\ast(2^{n-r}(2+\frac{n}{r})^r)\) for graphs having a dominating set of size \(r\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[2] Bodlaender, H. L.; Kloks, T.; Tan, R. B.; van Leeuwen, J., Approximations for lambda-colorings of graphs, Computer Journal, 47, 193-204 (2004) · Zbl 1039.68090
[3] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications (1999) · Zbl 0919.05001
[4] Calamoneri, T., The \(L(h, k)\)-labelling problem: a survey and annotated bibliography, Computer Journal, 49, 585-608 (2006)
[5] Chang, G. J.; Kuo, D., The \(L(2, 1)\)-labeling problem on graphs, SIAM Journal of Discrete Mathematics, 9, 309-316 (1996) · Zbl 0860.05064
[6] Cygan, M.; Kowalik, L., Channel assignment via fast zeta transform, Information Processing Letters, 111, 727-730 (2011) · Zbl 1260.68170
[7] Eggeman, N.; Havet, F.; Noble, S., \(k-L(2, 1)\)-labelling for planar graphs is NP-complete for \(k \geq 4\), Discrete Applied Mathematics, 158, 1777-1788 (2010) · Zbl 1209.05211
[8] Fiala, J.; Golovach, P.; Kratochvíl, J., Distance constrained labelings of graphs of bounded treewidth, (Proceedings of ICALP 2005. Proceedings of ICALP 2005, LNCS, vol. 3580 (2005)), 360-372 · Zbl 1082.68080
[9] Fiala, J.; Kloks, T.; Kratochvíl, J., Fixed-parameter complexity of \(\lambda \)-labelings, Discrete Applied Mathematics, 113, 59-72 (2001) · Zbl 0982.05085
[10] Fiala, J.; Kratochvíl, J., Locally constrained graph homomorphisms—structure, complexity, and applications, Computer Science Review, 2, 97-111 (2008) · Zbl 1302.05122
[11] Fomin, F. V.; Grandoni, F.; Kratsch, D., Measure and conquer: domination—a case study, (Proceedings of ICALP 2005. Proceedings of ICALP 2005, LNCS, vol. 3380 (2005)), 192-203 · Zbl 1082.68866
[12] Fomin, F. V.; Grandoni, F.; Kratsch, D., A measure and conquer approach for the analysis of exact algorithms, Journal of the ACM, 56, 5, 25:1-25:32 (2009) · Zbl 1325.68311
[13] Fomin, F. V.; Kratsch, D., Exact Exponential Algorithms (2010), Springer · Zbl 1370.68002
[14] Griggs, J. R.; Král, D., Graph labellings with variable weights, a survey, Discrete Applied Mathematics, 157, 2646-2658 (2009) · Zbl 1211.05145
[15] Griggs, J. R.; Yeh, R. K., Labelling graphs with a condition at distance 2, SIAM Journal of Discrete Mathematics, 5, 586-595 (1992) · Zbl 0767.05080
[17] Hasunuma, T.; Ishii, T.; Ono, H.; Uno, Y., A linear time algorithm for \(L(2, 1)\)-labeling of trees, (Proceedings of ESA 2009. Proceedings of ESA 2009, LNCS, vol. 5757 (2009)), 35-46 · Zbl 1256.05234
[19] Havet, F.; Klazar, M.; Kratochvíl, J.; Kratsch, D.; Liedloff, M., Exact algorithms for \(L(2, 1)\)-labeling of graphs, Algorithmica, 59, 169-194 (2011) · Zbl 1213.68455
[20] Janczewski, R.; Kosowski, A.; Małafiejski, M., The complexity of the \(L(p, q)\)-labeling problem for bipartite planar graphs of small degree, Discrete Mathematics, 309, 3270-3279 (2009) · Zbl 1205.05225
[21] Junosza-Szaniawski, K.; Kratochvíl, J.; Liedloff, M.; Rossmanith, P.; Rzążewski, P., Fast exact algorithm for \(L(2, 1)\)-labeling of graphs, (Proceedings of TAMC 2011. Proceedings of TAMC 2011, LNCS, vol. 6648 (2011)), 82-93 · Zbl 1333.05292
[22] Junosza-Szaniawski, K.; Rzążewski, P., On improved exact algorithms for \(L(2, 1)\)-labeling of graphs, (Proceedings of IWOCA 2010. Proceedings of IWOCA 2010, LNCS, vol. 6460 (2011)), 34-37 · Zbl 1295.05205
[23] Junosza-Szaniawski, K.; Rzążewski, P., On the complexity of exact algorithm for \(L(2, 1)\)-labeling of graphs, Information Processing Letters, 111, 697-701 (2011) · Zbl 1260.05162
[24] Král’, D., Channel assignment problem with variable weights, SIAM Journal on Discrete Mathematics, 20, 690-704 (2006) · Zbl 1146.94003
[25] Kratochvíl, J.; Kratsch, D.; Liedloff, M., Exact algorithms for \(L(2, 1)\)-labeling of graphs, (Proceedings of MFCS 2007. Proceedings of MFCS 2007, LNCS, vol. 4708 (2007)), 513-524 · Zbl 1147.05310
[27] van Rooij, J. M.M.; Bodlaender, H. L.; Rossmanith, P., Dynamic programming on tree decompositions using generalised fast subset convolution, (Proceedings of ESA 2009. Proceedings of ESA 2009, LNCS, vol. 5757 (2009)), 566-577 · Zbl 1256.68157
[28] Strassen, V., Gaussian elimination is not optimal, Numerische Mathematik, 13, 354-356 (1969) · Zbl 0185.40101
[29] Yeh, R., A survey on labeling graphs with a condition at distance two, Discrete Mathematics, 306, 1217-1231 (2006) · Zbl 1094.05047
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.