Show simple item record

dc.contributor.author
Gatto, Michael
dc.contributor.author
Jacob, Riko
dc.contributor.author
Peeters, Leon
dc.contributor.author
Schöbel, Anita
dc.date.accessioned
2017-08-10T13:15:28Z
dc.date.available
2017-06-10T19:31:14Z
dc.date.available
2017-08-10T13:15:28Z
dc.date.issued
2004
dc.identifier.uri
http://hdl.handle.net/20.500.11850/69780
dc.identifier.doi
10.3929/ethz-a-006759907
dc.description.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. We model the underlying transportation network as a directed acyclic graph, where edges represent trains, and weighted paths represent passenger flows. Given initial delays of some of the passenger paths, our goal is to decide which edges wait for delayed passenger paths, such that the sum of all passenger delays is minimized. 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 edges 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.
en_US
dc.format
application/pdf
dc.language.iso
en
en_US
dc.publisher
ETH, Department of Computer Science
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
COMPLEXITY CLASSES (THEORETICAL COMPUTER SCIENCE)
en_US
dc.subject
COMPUTER APPLICATIONS IN TRAFFIC AND TRANSPORTATION
en_US
dc.subject
COMPUTERANWENDUNGEN IN VERKEHR UND TRANSPORT
en_US
dc.subject
KOMPLEXITÄTSKLASSEN (THEORETISCHE INFORMATIK)
en_US
dc.title
Computational Complexity of Delay Management
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
Technical report
ethz.journal.volume
456
en_US
ethz.size
15 p.
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.identifier.nebis
006759907
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science
en_US
ethz.date.deposited
2017-06-10T19:34:36Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp593650d36f03e15941
ethz.identifier.importid
imp59366b14dcb2d74757
ethz.ecolpid
eth:4786
ethz.ecitpid
pub:110487
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-18T20:28:14Z
ethz.rosetta.lastUpdated
2020-02-15T06:42:19Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Computational%20Complexity%20of%20Delay%20Management&rft.jtitle=Technical%20report&rft.date=2004&rft.volume=456&rft.au=Gatto,%20Michael&Jacob,%20Riko&Peeters,%20Leon&Sch%C3%B6bel,%20Anita&rft.genre=report&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record