Skip to main content
Top
Published in: Journal of Combinatorial Optimization 1/2013

01-07-2013

On the union of intermediate nodes of shortest paths

Authors: Xiang Li, Xiaodong Hu, Wonjun Lee

Published in: Journal of Combinatorial Optimization | Issue 1/2013

Log in

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

search-config
loading …

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.

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!

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!

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!

Literature
go back to reference Feige U (1996) A threshold of lnn for approximating set-cover. In: Proc 28th ACM symposium on theory of computing, pp 314–318 Feige U (1996) A threshold of lnn for approximating set-cover. In: Proc 28th ACM symposium on theory of computing, pp 314–318
go back to reference Willson J, Gao X, Qu Z, Zhu Y, Li Y, Wu W (2009) Efficient distributed algorithms for topology control problem with shortest path constraints. Discrete Math, Algorithms Appl 1(4):437–461 MathSciNetMATHCrossRef Willson J, Gao X, Qu Z, Zhu Y, Li Y, Wu W (2009) Efficient distributed algorithms for topology control problem with shortest path constraints. Discrete Math, Algorithms Appl 1(4):437–461 MathSciNetMATHCrossRef
go back to reference Wu J, Li H (1999) On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd ACM international workshop on discrete algorithms and methods for mobile computing and communications, pp 7–14 Wu J, Li H (1999) On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd ACM international workshop on discrete algorithms and methods for mobile computing and communications, pp 7–14
Metadata
Title
On the union of intermediate nodes of shortest paths
Authors
Xiang Li
Xiaodong Hu
Wonjun Lee
Publication date
01-07-2013
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 1/2013
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-011-9436-9

Other articles of this Issue 1/2013

Journal of Combinatorial Optimization 1/2013 Go to the issue

Premium Partner