Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

02.01.2019

Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem

Zeitschrift:
Journal of Combinatorial Optimization
Autoren:
Mattia D’Emidio, Luca Forlizzi, Daniele Frigioni, Stefano Leucci, Guido Proietti
Wichtige Hinweise
The results presented in this work have been announced in a preliminary form in D’Emidio et al. (2016). This research has partially supported by the Italian National Group for Scientific Computation GNCS-INdAM.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

Given an n-vertex non-negatively real-weighted graph G, whose vertices are partitioned into a set of k clusters, a clustered network design problem on G consists of solving a given network design optimization problem on G, subject to some additional constraints on its clusters. In particular, we focus on the classic problem of designing a single-source shortest-path tree, and we analyse its computational hardness when in a feasible solution each cluster is required to form a subtree. We first study the unweighted case, and prove that the problem is \({\textsf {NP}}\)-hard. However, on the positive side, we show the existence of an approximation algorithm whose quality essentially depends on few parameters, but which remarkably is an O(1)-approximation when the largest out of all the diameters of the clusters is either O(1) or \(\varTheta (n)\). Furthermore, we also show that the problem is fixed-parameter tractable with respect to k or to the number of vertices that belong to clusters of size at least 2. Then, we focus on the weighted case, and show that the problem can be approximated within a tight factor of O(n), and that it is fixed-parameter tractable as well. Finally, we analyse the unweighted single-pair shortest path problem, and we show it is hard to approximate within a (tight) factor of \(n^{1-\epsilon }\), for any \(\epsilon >0\).

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

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

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

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise