Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.07.2013 | Ausgabe 1/2013

Journal of Combinatorial Optimization 1/2013

On the union of intermediate nodes of shortest paths

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 1/2013
Autoren:
Xiang Li, Xiaodong Hu, Wonjun Lee

Abstract

Consider a connected graph G=(V,E). For a pair of nodes u and v, denote by M uv the set of intermediate nodes of a shortest path between u and v. We are intertested in minimization of the union ⋃ u,vV M uv . We will show that this problem is NP-hard and cannot have polynomial-time ρlnδ-approximation for 0<ρ<1 unless NP⊆DTIME(n O(loglogn)) where δ is the maximum node degree of input graph. We will also construct a polynomial-time \(H(\frac{\delta (\delta -1)}{2})\)-approximation for the problem where H(⋅) is the harmonic function.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2013

Journal of Combinatorial Optimization 1/2013 Zur Ausgabe

Premium Partner

    Bildnachweise