User: Guest  Login
Title:

The undirected two disjoint shortest paths problem

Document type:
Zeitschriftenaufsatz
Author(s):
Gottschau, Marinus; Kaiser, Marcus; Waldmann, Clara
Non-TUM Co-author(s):
nein
Cooperation:
-
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...     »
Keywords:
Disjoint paths, Disjoint shortest paths, Dynamic programming, Mixed graphs
Intellectual Contribution:
Discipline-based Research
Journal title:
Operations Research Letters
Journal listet in FT50 ranking:
nein
Year:
2019
Journal volume:
47
Journal issue:
1
Pages contribution:
70 - 75
Fulltext / DOI:
doi:10.1016/j.orl.2018.11.011
Print-ISSN:
0167-6377
Judgement review:
0
Key publication:
Nein
Peer reviewed:
Ja
International:
Ja
Book review:
Nein
Commissioned:
not commissioned
Professional Journal:
Ja
Technology:
Nein
Interdisciplinarity:
Nein
Mission statement:
;
Ethics and Sustainability:
Nein
 BibTeX
versions