Computing and Listing st-Paths in Subway Networks

Abstract : Given a set of paths (called lines) L, a subway network is a graph GL = (V, A) where V contains exactly the vertices and arcs of every line l ∈ L. An st-route is a pair (π, γ) where γ = (l1,. .. , l h) is a line sequence and π is an st-path in GL which is the concatena-tion of subpaths of the lines l1,. .. , l h , in this order. We study three related problems concerning traveling from s to t in GL. We present an efficient (i.e., polynomial-time) algorithm for computing an st-route (π, γ) where |γ| (i.e., the number of line changes plus one) is minimum among all st-routes. We show 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. Finally, given an integer β, we present an algorithm for enumerating all st-paths π for which a route (π, γ) with |γ| ≤ β exists, and show that the running time of this algorithm is polynomial with respect to both input and output size.
Document type :
Conference papers
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/hal-01348869
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, July 26, 2016 - 9:04:31 AM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM

File

bounded_turns_paths.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Kateřina Böhmová, Matúš Mihalák, Tobias Pröger, Gustavo Sacomoto, Marie-France Sagot, et al.. Computing and Listing st-Paths in Subway Networks. CSR 2016 - 11th International Computer Science Symposium in Russia, Jun 2016, St. Petersburg, Russia. pp.102-116, ⟨10.1007/978-3-319-34171-2_8⟩. ⟨hal-01348869⟩

Share

Metrics

Record views

138

Files downloads

107