Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Approximations for the Max k-Colored Clustering Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Linear-Time Approximation Algorithms for Unit Disk Graphs

Authors : Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, Celina M. H. de Figueiredo

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time \((4\,+\,\varepsilon )\)-approximations to the maximum-weight independent set and the minimum dominating set, bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation factors. Furthermore, we present an alternative linear-time approximation scheme for the minimum vertex cover, which could be obtained by an indirect application of our method.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Optimal Online and Offline Algorithms for Robot-Assisted Restoration of Barrier Coverage
next chapter The Minimum Feasible Tileset Problem
Footnotes
1
Note that the Four-Color Theorem is only used in the argument, and no coloring is ever computed by the algorithm.
 
Literature
1.
Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. Cambridge University Press, Cambridge (2005)
2.
3.
Bentley, J., Stanat, D., Williams Jr, E.H.: The complexity of finding fixed-radius near neighbors. Inf. Process. Lett. 6(6), 209–212 (1977)CrossRefMATHMathSciNet
4.
5.
da Fonseca, G.D., de Figueiredo, C.M.H., Sá, V.G.P., Machado, R.C.S.: Efficient sub-5 approximations for minimum dominating sets in unit disk graphs. WAOA 2012, Theor. Comput. Sci. 540–541, 70–81 (2014)
6.
De, M., Das, G., Carmi, P., Nandy, S.: Approximation algorithms for a variant of discrete piercing set problem for unit disks. Int. J. Comput. Geom. Appl. 6(23), 461–477 (2013)CrossRefMathSciNet
7.
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130–136 (1985)CrossRefMATHMathSciNet
8.
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26, 238–274 (1998)CrossRefMATHMathSciNet
9.
Jallu, R.K., Prasad, P.R., Das, G.K.: Minimum dominating set for a point set in \(\mathbb{R}^2\). preprint, arXiv:​1312.​7243 (2014)
10.
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(2), 59–68 (1995)CrossRefMATHMathSciNet
11.
Marx, D.: Efficient approximation schemes for geometric problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 448–459. Springer, Heidelberg (2005) CrossRef
12.
Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194–200. Springer, Heidelberg (2000) CrossRef
13.
Nieberg, T., Hurink, J., Kern, W.: Approximation schemes for wireless networks. ACM Trans. Algorithms 4(4), 49:1–49:17 (2008)CrossRefMathSciNet
Metadata
Title
Linear-Time Approximation Algorithms for Unit Disk Graphs
Authors
Guilherme D. da Fonseca
Vinícius G. Pereira de Sá
Celina M. H. de Figueiredo
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-18262-9

Electronic ISBN: 978-3-319-18263-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-18263-6_12

Premium Partner

    Image Credits