Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Improved Approximations for the Max k-Colored Clustering Problem Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Linear-Time Approximation Algorithms for Unit Disk Graphs

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

Erschienen in: Approximation and Online Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Optimal Online and Offline Algorithms for Robot-Assisted Restoration of Barrier Coverage
Nächstes Kapitel The Minimum Feasible Tileset Problem
Fußnoten
1
Note that the Four-Color Theorem is only used in the argument, and no coloring is ever computed by the algorithm.
 
Literatur
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
Metadaten
Titel
Linear-Time Approximation Algorithms for Unit Disk Graphs
verfasst von
Guilherme D. da Fonseca
Vinícius G. Pereira de Sá
Celina M. H. de Figueiredo
Copyright-Jahr
2015
Buch
Approximation and Online Algorithms

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

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

Copyright-Jahr: 2015

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