Computing and Listing st-Paths in Public Transportation Networks
| Autor: | Gustavo Sacomoto, Luca Häfliger, Marie-France Sagot, Kateřina Böhmová, Matúš Mihalák, Tobias Pröger |
|---|---|
| Přispěvatelé: | RS: FSE DACS NSO, DKE Scientific staff |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Sequence
Polynomial 021103 operations research Concatenation 0211 other engineering and technologies Public transportation 0102 computer and information sciences 02 engineering and technology Directed graph 01 natural sciences Theoretical Computer Science Combinatorics Listing algorithm NP-hardness Computational Theory and Mathematics 010201 computation theory & mathematics 11. Sustainability Line (geometry) Path (graph theory) Theory of computation Order (group theory) K SHORTEST PATHS Mathematics |
| Zdroj: | Theory of Computing Systems, 62 (3) Theory of Computing Systems, 62(3), 600-621. Springer Verlag |
| ISSN: | 1432-4350 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink