Vertex Disjoint Paths for Dispatching in Railways
2010 | book part. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Cite this publication
Vertex Disjoint Paths for Dispatching in Railways
Flier, H.; Schöbel, A. ; Mihalak, M.; Widmayer, P.& Zych, A. (2010)
In:Erlebach, Thomas; Lübbecke, Marco (Eds.), 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) pp. 61-73. DOI: https://doi.org/10.4230/OASIcs.ATMOS.2010.61
Documents & Media
Details
- Authors
- Flier, Holger; Schöbel, Anita ; Mihalak, Matus; Widmayer, Peter; Zych, Anna
- Editors
- Erlebach, Thomas; Lübbecke, Marco
- Abstract
- We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routingin- rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a p-approximation algorithm for the routing-in-rounds problem, where p is the maximum number of alternative paths for a terminal pair.
- Issue Date
- 2010
- Organization
- Fakultät für Mathematik und Informatik
- Language
- English
