User: Guest  Login
Document type:
Zeitschriftenaufsatz 
Author(s):
Gottschau, Marinus; Kaiser, Marcus; Waldmann, Clara 
Non-TUM Co-author(s):
nein 
Cooperation:
Title:
The undirected two disjoint shortest paths problem 
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 len...    »
 
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:
Pages contribution:
70 - 75 
Print-ISSN:
0167-6377 
Key publication:
Nein 
Peer reviewed:
Ja 
International:
Ja 
Book review:
Nein 
Commissioned:
not commissioned 
Professional Journal:
Ja 
Interdisciplinarity:
Nein 
Mission statement:
Ethics and Sustainability:
Nein