The computational complexity of delay management extended abstract
2005 | conference paper. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Cite this publication
The computational complexity of delay management extended abstract
Gatto, M.; Jacob, R.; Peeters, L. & Schobel, A. (2005)
Graph-theoretic concepts in computer science pp. 227-238. 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Metz, France.
Berlin: Springer.
Documents & Media
Details
- Authors
- Gatto, M.; Jacob, R.; Peeters, L.; Schobel, A.
- Abstract
- Delay management for public transport consists of deciding whether vehicles should wait for delayed transferring passengers, with the objective of minimizing the overall passenger discomfort. This paper classifies the computational complexity of delay management problems with respect to various structural parameters, such as the maximum number of passenger transfers, the graph topology, and the capability of trains to reduce delays. Our focus is to distinguish between polynomially solvable and NP-complete problem variants. To that end, we show that even fairly restricted versions of the delay management problem are hard to solve.
- Issue Date
- 2005
- Publisher
- Springer
- Conference
- 31st International Workshop on Graph-Theoretic Concepts in Computer Science
- Series
- Lecture Notes in Computer Science
- ISBN
- 3-540-31000-2
978-3-540-31000-6 - Conference Place
- Metz, France
- Event start
- 2005-06-23
- Event end
- 2005-06-25