Show simple item record

The Computational Complexity of Delay Management

dc.contributor.authorGatto, Michael
dc.contributor.authorJacob, Riko
dc.contributor.authorPeeters, Leon
dc.contributor.authorSchöbel, Anita
dc.contributor.editorKratsch, Dieter
dc.date.accessioned2010-11-16T08:50:35Z
dc.date.available2010-11-16T08:50:35Z
dc.date.issued2005
dc.identifier.urihttp://resolver.sub.uni-goettingen.de/purl?gs-1/5717
dc.description.abstractDelay 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 MediaObjects/InlineFigure1.png-complete problem variants. To that end, we show that even fairly restricted versions of the delay management problem are hard to solve.
dc.format.extent227-238
dc.language.isoeng
dc.publisherSpringer
dc.relation.ispartofGraph-Theoretic Concepts in Computer Science
dc.rightsopenAccess
dc.subjectDelay Management
dc.subject.ddc510
dc.titleThe Computational Complexity of Delay Management
dc.typeanthologyArticle
dc.type.versionsubmittedVersion
dc.type.subtypeanthologyArticle
dc.relation.ispartofseriesLecture Notes in Computer Science; 3787
dc.description.statuspeerReviewed


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record