On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs. (English) Zbl 1260.05162
Summary: \(L(2,1)\)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least \(2\) and vertices in distance \(2\) get different labels. It is known that for any \(k\geq 4\) it is NP-complete to determine if a graph has a \(L(2,1)\)-labeling with no label greater than \(k\).
In this paper we present a new bound on complexity of an algorithm for finding an optimal \(L(2,1)\)-labeling (i.e. an \(L(2,1)\)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from \(O^{\ast}(3.5616^{n})\) to \(O^{\ast}(3.2361^{n})\). Moreover, we establish a lower complexity bound of the presented algorithm, which is \(\Omega ^{\ast}(3.0739^{n})\).
In this paper we present a new bound on complexity of an algorithm for finding an optimal \(L(2,1)\)-labeling (i.e. an \(L(2,1)\)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from \(O^{\ast}(3.5616^{n})\) to \(O^{\ast}(3.2361^{n})\). Moreover, we establish a lower complexity bound of the presented algorithm, which is \(\Omega ^{\ast}(3.0739^{n})\).
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 68W40 | Analysis of algorithms |
Keywords:
analysis of algorithms; combinatorial problems; graph algorithms; \(L(2,1)\)-labeling; list labeling; graph coloring model; exact algorithmReferences:
| [1] | Bulterman, R. W.; van der Sommen, F. W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A. J.M.; Feijen, W. H.J., On computing a longest path in a tree, Information Processing Letters, 81, 93-96 (2002) · Zbl 1032.68671 |
| [2] | Eggeman, N.; Havet, F.; Noble, S., \(k-L(2, 1)\)-labelling for planar graphs is NP-complete, Discrete Applied Mathematics, 158, 1777-1788 (2010) · Zbl 1209.05211 |
| [3] | Fiala, J.; Kratochvíl, J., On the computational complexity of the \(L(2, 1)\)-labeling problem for regular graphs, (ICTCS Proc.. ICTCS Proc., LNCS, vol. 3701 (2005)), 228-236 · Zbl 1171.68612 |
| [4] | Fiala, J.; Kratochvíl, J.; Kloks, T., Fixed-parameter complexity of \(λ\)-labelings, Discrete Applied Mathematics, 113, 59-72 (2001) · Zbl 0982.05085 |
| [5] | Griggs, J. R.; Yeh, R. K., Labeling graphs with a condition on distance 2, SIAM J. Discrete Math., 5, 586-595 (1992) · Zbl 0767.05080 |
| [6] | Hale, W. K., Frequency assignment: Theory and applications, Proc. of the IEEE, 68, 1497-1514 (1980) |
| [7] | 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 |
| [8] | K. Junosza-Szaniawski, J. Kratochvíl, M. Liedloff, P. Rossmanith, P. Rzążewski, Fast exact algorithm for \(L(2, 1)\); K. Junosza-Szaniawski, J. Kratochvíl, M. Liedloff, P. Rossmanith, P. Rzążewski, Fast exact algorithm for \(L(2, 1)\) |
| [9] | Junosza-Szaniawski, K.; Rzążewski, P., On improved exact algorithms for \(L(2, 1)\) labeling of graphs, (IWOCA 2010 Proc.. IWOCA 2010 Proc., LNCS, vol. 6460 (2011)), 34-37 · Zbl 1295.05205 |
| [10] | Král, D., An exact algorithm for channel assignment problem, Discrete Applied Mathematics, 145, 326-331 (2005) · Zbl 1084.05069 |
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.
