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:
On the Capture Time of Cops and Robbers Game on a Planar Graph Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Computing a Tree Having a Small Vertex Cover

verfasst von : Takuro Fukunaga, Takanori Maehara

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper, we consider a new Steiner tree problem. This problem defines the weight of a Steiner tree as the minimum weight of vertex covers in the tree, and seeks a minimum-weight Steiner tree in a given vertex-weighted undirected graph. Since it is included by the Steiner tree activation problem, the problem admits an \(O(\log n)\)-approximation algorithm in general graphs with n vertices. This approximation factor is tight because it is known to be NP-hard to achieve an \(o(\log n)\)-approximation for the problem with general graphs. In this paper, we present constant-factor approximation algorithms for the problem with unit disk graphs and with graphs excluding a fixed minor.

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 On Strong Tree-Breadth
Nächstes Kapitel On the Approximability of Partial VC Dimension
Literatur
1.
Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, 6 (2013)MathSciNetCrossRefMATH
2.
Goemans, M.X., Olver, N., Rothvoß, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic steiner tree relaxations. In: STOC, pp. 1161–1176 (2012)
3.
Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. In: IPCO, pp. 323–332 (1993)
4.
Perlman, R.J.: An algorithm for distributed computation of a spanningtree in an extended LAN. In: SIGCOMM, pp. 44–53 (1985)
5.
Panigrahi, D.: Survivable network design problems in wireless networks. In: SODA, pp. 1014–1027 (2011)
6.
7.
Demaine, E.D., Hajiaghayi, M., Klein, P.N.: Node-weighted Steiner tree and group Steiner tree in planar graphs. ACM Trans. Algorithms 10, 13 (2014)MathSciNetMATH
8.
Zou, F., Li, X., Gao, S., Wu, W.: Node-weighted Steiner tree approximation in unit disk graphs. J. Comb. Opt. 18, 342–349 (2009)MathSciNetCrossRefMATH
9.
Zou, F., Li, X., Kim, D., Wu, W.: Two constant approximation algorithms for node-weighted steiner tree in unit disk graphs. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 278–285. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85097-7_​26 CrossRef
10.
Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX/RANDOM -2006. LNCS, vol. 4110, pp. 3–14. Springer, Heidelberg (2006). doi:10.​1007/​11830924_​3 CrossRef
11.
Huang, L., Li, J., Shi, Q.: Approximation algorithms for the connected sensor cover problem. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 183–196. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-21398-9_​15 CrossRef
12.
Zou, F., Wang, Y., Xu, X., Li, X., Du, H., Wan, P., Wu, W.: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor. Comp. Sci. 412, 198–208 (2011)MathSciNetCrossRefMATH
13.
Eisenbrand, F., Grandoni, F., Rothvoß, T., Schäfer, G.: Connected facility location via random facility sampling and core detouring. J. Comp. Sys. Sci. 76, 709–726 (2010)MathSciNetCrossRefMATH
14.
15.
Cheng, X., Huang, X., Li, D., Wu, W., Du, D.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)MathSciNetCrossRefMATH
16.
17.
18.
19.
Fonseca, G.D., Sá, V.G.P., Figueiredo, C.M.H.: Linear-time approximation algorithms for unit disk graphs. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 132–143. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-18263-6_​12
Metadaten
Titel
Computing a Tree Having a Small Vertex Cover
verfasst von
Takuro Fukunaga
Takanori Maehara
Copyright-Jahr
2016
Buch
Combinatorial Optimization and Applications

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

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

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-48749-6_6

Premium Partner

    Bildnachweise