Benutzer: Gast  Login
Titel:

The undirected two disjoint shortest paths problem

Dokumenttyp:
Zeitschriftenaufsatz
Autor(en):
Gottschau, Marinus; Kaiser, Marcus; Waldmann, Clara
Nicht-TUM Koautoren:
nein
Kooperation:
-
Abstract:
The k disjoint shortest paths problem (k-DSPP) on a graph with k source–sink pairs (si,ti) asks if there exist k pairwise edge- or vertex-disjoint shortest si–ti-paths. It is known to be NP-complete if k is part of the input. Restricting to 2-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for 2-DSPP on undirected graphs with non-negative edge lengt...     »
Stichworte:
Disjoint paths, Disjoint shortest paths, Dynamic programming, Mixed graphs
Intellectual Contribution:
Discipline-based Research
Zeitschriftentitel:
Operations Research Letters
Journal gelistet in FT50 Ranking:
nein
Jahr:
2019
Band / Volume:
47
Heft / Issue:
1
Seitenangaben Beitrag:
70 - 75
Volltext / DOI:
doi:10.1016/j.orl.2018.11.011
Print-ISSN:
0167-6377
Urteilsbesprechung:
0
Key publication:
Nein
Peer reviewed:
Ja
International:
Ja
Book review:
Nein
commissioned:
not commissioned
Professional Journal:
Ja
Technology:
Nein
Interdisziplinarität:
Nein
Leitbild:
;
Ethics und Sustainability:
Nein
 BibTeX
Versionen