P.K. Agarwal, M. van Kreveld, S. Suri, Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl. 11, 209–218 (1998)

Article  MathSciNet  MATH  Google Scholar 

K.M. Alzoubi, P. Wan, O. Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne (2002)

MATH  Google Scholar 

E.M. Arkin, M.M. Halldǒrsson, R. Hassin, Approximating the tree and tour covers of a graph. Inform. Process. Lett. 47, 275–282 (1993)

Google Scholar 

S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegegy, Proof verification and hardness of approximation problems, in Proceedings of 33rd Annual Symposium on Foundations of Computer Science (FOCS 1992), Pttsburgh (1992), pp. 14–23

Google Scholar 

B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, 7–9 Nov (IEEE, New York, 1983), pp. 254–273. J. ACM 41, 153–180 (1994)

Google Scholar 

R. Bar-Yehuda, S. Even, On approximating a vertex cover for planar graphs, in STOC (1932), pp. 303–309

Google Scholar 

R. Bar-Yehuda, S. Even, A local-ratio theorem for approximating the weighted vertex cover problem. Inform. Process. Lett. 47, 275–282 (1993)

MathSciNet  MATH  Google Scholar 

P. Berman, T. Fujito, On approximation properties of the independent set problem for degree 3 graphs. Workshop on Algorithms and Data Structures. Lect. Notes Comput. Sci. 955, 449–460 (1995)

MathSciNet  MATH  Google Scholar 

P. Berman, B. Basgupta, S. Muthukrishnan, S. Ramaswami, Efficient approximation algorithms for tiling and packing problem with rectangles. J. Algorithms 41, 178–189 (2001)

Article  MathSciNet  MATH  Google Scholar 

V. Bharghavan, B. Das, Routing in ad hoc networks using minimum connected dominating sets, in International Conference on Communication, Montreal (1997)

MATH  Google Scholar 

V. Biló, I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, Geometric Clustering to Minimize the Sum of Cluster Sizes (ESA, 2005), pp. 460–471

Google Scholar 

J. Blum, M. Ding, A. Thaeler, X.Z. Cheng, Connected dominating set in sensor networks and MANETs, in Handbook of Combinatorial Optimization (Kluwer Academic Publishers, Dordrecht, 2004), pp. 329–369

MATH  Google Scholar 

H. Breu, D.G. Kirkpatrick, Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9, 3–24 (1998)

Article  MathSciNet  MATH  Google Scholar 

S. Butenko, S. Kahruman-Anderoglu, O. Ursulenko, On connected domination in unit ball graphs. Optim. Lett. 5, 195–205 (2011)

Article  MathSciNet  MATH  Google Scholar 

M. Cadei, M.X. Cheng, X. Cheng, D. Du, Connected domination in ad hoc wireless networks, in Proceedings of the Sixth International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne (2002)

MATH  Google Scholar 

T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178–189 (2003)

Article  MathSciNet  MATH  Google Scholar 

Y.P. Chen, A.L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, in Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne (2002)

MATH  Google Scholar 

X. Cheng, X. Huang, D. Li, W. Wu, D. Du, A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)

Article  MathSciNet  MATH  Google Scholar 

B.N. Clark, C.J. Colbourn, D.S. Johnson, Unit disk graphs. Discrete Math. 86, 165–177 (1990)

Article  MathSciNet  MATH  Google Scholar 

B. Das, R. Sivakumar, V. Bharghavan, Routing in ad-hoc networks using a virtual backbone, in 6th International Conference on Computer Communications and Networks (IC3N’97) (1997), pp. 1–20

Google Scholar 

L. Ding, X.F. Gao, W.L. Wu, W. Lee, X. Zhu, D.-Z. Du. Distributed construction of connected dominating sets with minimum routing cost in wireless networks, in 2010 IEEE 30th International Conference on Distributed Computing Systems (IEEE, 2010), pp. 448–457

Google Scholar 

I. Dinur, S. Safra, On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439–485 (2005)

Article  MathSciNet  MATH  Google Scholar 

D.-Z. Du, Y. Zhang, Q. Feng, On better heuristic for Euclidean Steiner minimum trees, in Proceedings 32nd IEEE Symposium on Foundations of Computer Science (1991), pp. 431–439

Google Scholar 

T. Erlebach, K. Jansen, E. Seidel, Polynomial-time approximation schemes for geometric graphs, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA’01) (2001), pp. 671–679

Google Scholar 

T. Erlebach, K. Jansen, E. Seidel, Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302–1323 (2005)

Article  MathSciNet  MATH  Google Scholar 

B. Escoffier, L. Gourvès, J. Monnot, Complexity and approximation results for the connected vertex cover problem. Graph-Theoretic Concepts in Computer Science. Lect. Notes Comput. Sci. 4769, 202–213 (2007)

MathSciNet  MATH  Google Scholar 

U. Feige, A threshold of \(\ln n\) for approximating set cover, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC) (ACM Press, New York, 1996), pp. 314–318

Google Scholar 

T. Fujito, T. Doi, A 2-approximation NC algorithm for connected vertex cover and tree cover. Inform. Process. Lett. 90, 59–63 (2004)

Article  MathSciNet  MATH  Google Scholar 

S. Funke, M. Segal, A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Trans. Sensor Netw. 2, 444–453 (2006)

Article  MATH  Google Scholar 

X.F. Gao, W. Wang, Z. Zhang, S.W. Zhu, W.L. Wu, A PTAS for minimum d-hop connected dominating set in growth bounded graphs. Optim. Lett. 4, 321–333 (2010)

Article  MathSciNet  MATH  Google Scholar 

M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1978)

MATH  Google Scholar 

B. Gfeller, E. Vicari, A Faster distributed approximation scheme for the connected dominating set problem for growth-bounded graphs, in ADHOC-NOW 2007, ed. by E. Kranakis, J. Opatrny. LNCS, vol. 4686 (2007), pp. 59–C73

Google Scholar 

C. Glaßer, S. Reith, H. Vollmer, The complexity of base station positioning in cellular networks. Discrete Appl. Math. 148, 1–12 (2005)

Article  MathSciNet  MATH  Google Scholar 

T.F. Gonzalez, Covering a set of points in multidimensional space. Inform. Process. Lett. 40, 181–188 (1991)

Article  MathSciNet  MATH  Google Scholar 

S. Guha, S. Khuller, Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998)

Article  MathSciNet  MATH  Google Scholar 

D.S. Hochbaum, W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985)

Article  MathSciNet  MATH  Google Scholar 

D.S. Hochbaum, Approximation Algorithm for NP-Hard Problems (PWS, Boston, 1997)

MATH  Google Scholar 

H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26, 238–274 (1998)

Article  MathSciNet  MATH  Google Scholar 

K. Jansen, L. Porkolab, On preemptive resource constrained scheduling: polynomial-time approximation schemes. Integer Programming and Combinatorial Optimization. Lect. Notes Comput. Sci. 2337, 329–349 (2006)

MathSciNet  MATH  Google Scholar 

S.K. Jena, R.K. Jallu, G.K. Das, S.C. Nandy, The Generalized Independent and Dominating Set Problems on Unit Disk Graphs. arXiv preprint arXiv:2006.15381 (2020)

Google Scholar 

T. Jiang, E.B. Lawler, L.S. Wang, Aligning sequences via an evolutionary tree: complexity and algorithms, in Proceedings 26th ACM Symposium on Theory of Computing (1994), pp. 760–769

Google Scholar 

D.S. Johnson, Approximation algorithms for combinatorial problems. JCSS 9, 256–278 (1974)

MathSciNet  MATH  Google Scholar 

R.M. Karp, Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plane. Math. Oper. Res. 2, 209–224 (1977)

Article  MathSciNet  MATH  Google Scholar 

S. Khot, O. Regev, Vertex cover might be hard to approximate to within 2 − ε. J. Comput. Syst. Sci. 74, 335–349 (2008)