Vertex Disjoint Paths for Dispatching in Railways
OPEN ACCESS
Author / Producer
Date
2010
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
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 routing-in-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.
Permanent link
Publication status
published
External links
Book title
10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010)
Journal / series
Volume
14
Pages / Article No.
61 - 73
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
algorithms; approximation; complexity; graph theory; railways; routing; transportation
Organisational unit
03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)