Abstract
Given a graph, an L(2, 1)-labeling of the graph is an assignment \(\ell \) from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), \(|\ell (u) - \ell (v)| \ge 2\) if u and v are adjacent, and \(\ell (u) \ne \ell (v)\) if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the span of \(\ell \) (i.e., \(\max _{u \in V}(\ell (u)) - \min _{u \in V}(\ell (u)) + 1\)). In this paper, we propose a new polynomial-time 116/13-approximation algorithm for L(2, 1)-labeling of unit disk graphs. This improves the previously best known ratio 12.
This work is partially supported by KAKENHI 17K19960, 17H01698.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bodlaender, H.L., Kloks, T., Tan, R.B., Van Leeuwen, J.: Approximations for \(\lambda \)-colorings of graphs. Comput. J. 47(2), 193–204 (2004)
Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1), 3–24 (1998)
Calamoneri, T.: The \({L} (h, k)\)-labelling problem: an updated survey and annotated bibliography. Comput. J. 54(8), 1344–1371 (2011)
Chang, G.J., Kuo, D.: The \({L}(2,1)\)-labeling problem on graphs. SIAM J. Discrete Math. 9(2), 309–316 (1996)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1), 165–177 (1990)
Fiala, J., Fishkin, A.V., Fomin, F.: On distance constrained labeling of disk graphs. Theor. Comput. Sci. 326(1), 261–292 (2004)
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). https://doi.org/10.1007/11523468_30
Fiala, J., Kloks, T., Kratochvíl, J.: Fixed-parameter complexity of \(\lambda \)-labelings. Discrete Appl. Math. 113(1), 59–72 (2001)
Gonçalves, D.: On the \({L}(p,1)\)-labelling of graphs. Discrete Math. 308(8), 1405–1414 (2008). Third European Conference on Combinatorics
Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5(4), 586–595 (1992)
Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497–1514 (1980)
Hasunuma, T., Ishii, T., Ono, H., Uno, Y.: A linear time algorithm for \({L} (2, 1)\)-labeling of trees. Algorithmica 66(3), 654–681 (2013)
Hasunuma, T., Ishii, T., Ono, H., Uno, Y.: Algorithmic aspects of distance constrained labeling: a survey. Int. J. Netw. Comput. 4(2), 251–259 (2014)
Junosza-Szaniawski, K., Rzażewski, P., Sokół, J., Wesek, K.: Coloring and \(L(2, 1)\)-labeling of unit disk intersection graphs. In: European Workshop on Computational Geometry (EuroCG), pp. 83–86 (2016)
Koller, A.E.: The frequency assignment problem. Ph.D. thesis. Brunel University, School of Information Systems, Computing and Mathematics (2005)
Roberts, F.S.: \({T}\)-colorings of graphs: recent results and open problems. Discrete Math. 93(2), 229–245 (1991)
Shao, Z., Yeh, R.K., Poon, K.K., Shiu, W.C.: The \({L}(2,1)\)-labeling of \({K}_{1, n}\)-free graphs and its applications. Appl. Math. Lett. 21(11), 1188–1193 (2008)
Yeh, R.K.: A survey on labeling graphs with a condition at distance two. Discrete Math. 306(12), 1217–1231 (2006)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Ono, H., Yamanaka, H. (2019). A 116/13-Approximation Algorithm for L(2, 1)-Labeling of Unit Disk Graphs. In: Catania, B., Královič, R., Nawrocki, J., Pighizzini, G. (eds) SOFSEM 2019: Theory and Practice of Computer Science. SOFSEM 2019. Lecture Notes in Computer Science(), vol 11376. Springer, Cham. https://doi.org/10.1007/978-3-030-10801-4_30
Download citation
DOI: https://doi.org/10.1007/978-3-030-10801-4_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-10800-7
Online ISBN: 978-3-030-10801-4
eBook Packages: Computer ScienceComputer Science (R0)