Abstract
An L(p,q)-labeling of a graph is a labeling of its vertices by nonnegative integers such that the labels of adjacent vertices differ by at least p and the labels of vertices at distance 2 differ by at least q. The span of such a labeling is the maximum label used. Distance constrained labelings are an important graph theoretical approach to the Frequency Assignment Problem applied in mobile and wireless networks.
In this paper we show that determining the minimum span of an L(p,q)-labeling of a tree is NP-hard whenever q is not a divisor of p. This demonstrates significant difference in computational complexity of this problem for q = 1 and q > 1. In addition, we give a sufficient and necessary condition for the existence of an H(p,q)-labeling of a tree in the case when the metric on the label space is determined by a strongly vertex transitive graph H. This generalizes the problem of distance constrained labeling in cyclic metric, that was known to be solvable in polynomial time for trees.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)
Calamoneri, T.: The L(h,k)-labeling problem: A survey and annotated bibliography. Computer Journal 49(5), 585–608 (2006)
Chang, G.J., Ke, W.-T., Liu, D.D.-F., Yeh, R.K.: On L(d,1)-labelings of graphs. Discrete Mathematics 220(1–3), 57–66 (2000)
Chang, G.J., Kuo, D.: The L(2,1)-labeling problem on graphs. SIAM Journal on Discrete Mathematics 9(2), 309–316 (1996)
Fiala, J., Golovach, P.A., Kratochvíl, J.: Distance constrained labelings of graphs of bounded treewidth. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 360–372. Springer, Heidelberg (2005)
Fiala, J., Golovach, P. A., and Kratochvíl, J.: Distance constrained labelings of trees. Tech. Rep. ITI Series 2008–369, Charles University (2007)
Fiala, J., Kratochvíl, J.: Partial covers of graphs. Discussiones Mathematicae Graph Theory 22, 89–99 (2002)
Fiala, J., Kratochvíl, J., Kloks, T.: Fixed-parameter complexity of λ-labelings. Discrete Applied Mathematics 113(1), 59–72 (2001)
Fiala, J., Kratochvíl, J., Proskurowski, A.: Distance constrained labeling of precolored trees. In: Restivo, A., Ronchi Della Rocca, S., Roversi, L. (eds.) ICTCS 2001. LNCS, vol. 2202, pp. 285–292. Springer, Heidelberg (2001)
Fiala, J., Kratochvíl, J., Proskurowski, A.: Systems of distant representatives. Discrete Applied Mathematics 145(2), 306–316 (2005)
Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics 5(4), 586–595 (1992)
Harary, F.: Graph theory. Addison-Wesley Series in Mathematics IX. Addison-Wesley, Reading (1969)
Havet, F., Reed, B., Sereni, J.-S.: L(2,1)-labelling of graphs. In: Huang, S.-T. (ed.) Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pp. 621–630. SIAM, Philadelphia (2008)
Král, D.: Mixed hypergraphs and other coloring problems. Discrete Mathematics 307(7-8), 923–938 (2007)
Leese, R.A., Noble, S.D.: Cyclic labellings with constraints at two distances. Electronic Journal of Combinatorics 11(1) (2004)
Liu, D.D.-F., Zhu, X.: Circulant distant two labeling and circular chromatic number. Ars Combinatoria 69, 177–183 (2003)
Matoušek, J., Nešetřil, J.: Invitation to Discrete Mathematics. Oxford University Press, Oxford (1998)
Roberts, F.S.: T-colorings of graphs: recent results and open problems. Discrete Mathematics 93(2–3), 229–245 (1991)
Yeh, R.K.: A survey on labeling graphs with a condition at distance two. Discrete Mathematics 306(12), 1217–1231 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fiala, J., Golovach, P.A., Kratochvíl, J. (2008). Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol 5125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70575-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-70575-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70574-1
Online ISBN: 978-3-540-70575-8
eBook Packages: Computer ScienceComputer Science (R0)