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.
Type de document :
Communication dans un congrès
Alexander S. Kulikov ; Gerhard J. Woeginger CSR 2016 - 11th International Computer Science Symposium in Russia, Jun 2016, St. Petersburg, Russia. Springer, 9691, pp.102-116, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-34171-2_8〉
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01348869
Contributeur : Marie-France Sagot <>
Soumis le : mardi 26 juillet 2016 - 09:04:31
Dernière modification le : mardi 16 janvier 2018 - 15:45:45

Fichier

bounded_turns_paths.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. Alexander S. Kulikov ; Gerhard J. Woeginger CSR 2016 - 11th International Computer Science Symposium in Russia, Jun 2016, St. Petersburg, Russia. Springer, 9691, pp.102-116, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-34171-2_8〉. 〈hal-01348869〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

47