An 8-approximation algorithm for L(2,1)-labeling of unit disk graphs

Bertossi, 1995, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE/ACM Trans. Netw., 3, 441, 10.1109/90.413218 Bodlaender, 2004, Approximations for λ-colorings of graphs, Comput. J., 47, 193, 10.1093/comjnl/47.2.193 Breu, 1998, Unit disk graph recognition is NP-hard, Comput. Geom., 9, 3, 10.1016/S0925-7721(97)00014-X Calamoneri, 2011, The L(h,k)-labelling problem: an updated survey and annotated bibliography, Comput. J., 54, 1344, 10.1093/comjnl/bxr037 Calamoneri, 2004, L(h,1)-labeling subclasses of planar graphs, J. Parallel Distrib. Comput., 64, 414, 10.1016/j.jpdc.2003.11.005 Chang, 1996, The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math., 9, 309, 10.1137/S0895480193245339 Chybowska-Sokół, 2020, L(2,1)-labeling of disk intersection graphs, Discrete Appl. Math., 277, 71, 10.1016/j.dam.2019.08.020 Clark, 1990, Unit disk graphs, Discrete Math., 86, 165, 10.1016/0012-365X(90)90358-O Fiala, 2004, On distance constrained labeling of disk graphs, Theoret. Comput. Sci., 326, 261, 10.1016/j.tcs.2004.06.026 Fiala, 2005, Distance constrained labelings of graphs of bounded treewidth, 360 Gonçalves, 2008, On the L(p,1)-labelling of graphs, Discrete Math., 308, 1405, 10.1016/j.disc.2007.07.075 Griggs, 1992, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math., 5, 586, 10.1137/0405048 Hale, 1980, Frequency assignment: Theory and applications, Proc. IEEE, 68, 1497, 10.1109/PROC.1980.11899 Hasunuma, 2013, A linear time algorithm for L(2,1)-labeling of trees, Algorithmica, 66, 654, 10.1007/s00453-012-9657-z Hasunuma, 2014, Algorithmic aspects of distance constrained labeling: a survey, Int. J. Netw. Comput., 4, 251 Havet, 2012, Griggs and Yeh’s Conjecture and L(p,1)-labelings, SIAM J. Discrete Math., 26, 145, 10.1137/090763998 Junosza-Szaniawski, 2016, Coloring and L(2,1)-labeling of unit disk intersection graphs, 83 Koller, 2005 McCormick, 1983, Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem, Math. Program., 26, 153, 10.1007/BF02592052 Ono, 2019, A 116/13-approximation algorithm for L(2,1)-labeling of unit disk graphs, 379 Paul, 2015, L(2,1)-Labeling of interval graphs, J. Appl. Math. Comput., 49, 419, 10.1007/s12190-014-0846-6 Roberts, 1991, T-Colorings of graphs: recent results and open problems, Discrete Math., 93, 229, 10.1016/0012-365X(91)90258-4 Sen, 1997, A new model for scheduling packet radio networks, Wirel. Netw., 3, 71, 10.1023/A:1019128411323 Shao, 2008, The L(2,1)-labeling of K1,n-free graphs and its applications, Appl. Math. Lett., 21, 1188, 10.1016/j.aml.2007.12.020 Yeh, 2006, A survey on labeling graphs with a condition at distance two, Discrete Math., 306, 1217, 10.1016/j.disc.2005.11.029