Abstract
Given a set of directed paths (called lines) L, a public transportation network is a directed graph G L = (V L , A L ) which contains exactly the vertices and arcs of every line l ∈ L. An st-route is a pair (π, γ) where γ = 〈l 1,…, l h 〉 is a line sequence and π is an st-path in G L which is the concatenation of subpaths of the lines l 1,…, l h , in this order. Given a threshold β, we present an algorithm for listing all st-paths π for which a route (π, γ) with |γ| ≤ β exists, and we show that the running time of this algorithm is polynomial with respect to the input and the output size. We also present an algorithm for listing all line sequences γ with |γ| ≤ β for which a route (π, γ) exists, and show how to speed it up using preprocessing. Moreover, we show that for the problem of finding an st-route (π, γ) that minimizes the number of different lines in γ, even computing an o(log|V|) -approximation is NP-hard. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000128244Publication status
publishedExternal links
Journal / series
Theory of Computing SystemsVolume
Pages / Article No.
Publisher
SpringerSubject
Listing algorithm; NP-hardness; Public transportationFunding
138117 - Context Sensitive Information: Robust Optimization by Information Theoretic Regularization (SNF)
More
Show all metadata