Computing Constrained Shortest-Paths at Scale

References

• Abraham I, Delling D, Goldberg AV, Werneck RF (2011b) A hub-based labeling algorithm for shortest paths in road networks. Internat. Sympos. Experiment. Algorithms. Pardalos PM, Rebennack S eds. (Springer, Heidelberg, Germany), 6630:230–241.Google Scholar
• Abraham I, Fiat A, Goldberg AV, Werneck RF (2010) Highway dimension, shortest paths, and provably efficient algorithms. Proc. Twenty-First Annual ACM-SIAM Sympos. Discrete Algorithms. Aceto L, Henzinger M, Sgall J eds. (Springer, Heidelberg, Germany), 6675:690–699.Google Scholar
• Abraham I, Delling D, Fiat A, Goldberg AV, Werneck RF (2011a) Vc-dimension and shortest path algorithms. International Colloquium on Automata, Languages, and Progamming (Springer; New York), 690–699.Google Scholar
• Abraham I, Delling D, Fiat A, Goldberg AV, Werneck RF (2016) Highway dimension and provably efficient shortest path algorithms. J. ACM 63(5):41.Crossref, Google Scholar
• Babenko M, Goldberg AV, Kaplan H, Savchenko R, Weller M (2015) On the complexity of hub labeling. Internat. Sympos. Math. Foundations Comput. Sci. (Springer, Heidelberg, Germany), 7965:69–80.Google Scholar
• Barrett C, Bisset K, Holzer M, Konjevod G, Marathe M, Wagner D (2008) Engineering label-constrained shortest-path algorithms. Internat. Conf. Algorithmic Appl. Management.Google Scholar
• Bast H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF (2016) Route Planning in Transportation Networks. Algorithm Engineering (Springer, New York), 19–80.Google Scholar
• Becker A, Klein PN, Saulpic D (2018) Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. 26th Annual Eur. Sympos. Algorithms (ESA 2018) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik).Google Scholar
• Blum J (2019) Hierarchy of transportation network parameters and hardness results. Jansen BMP, Telle JA, eds., 14th Internat. Sympos. Parameterized Exact Computation (IPEC 2019), number 148 in Leibniz International Proceedings in Informatics (LIPIcs) (Wadern: Schloss Dagstuhl, Leibniz-Zentrum für Informatik), Article Number 4.Google Scholar
• Clawson Z, Ding X, Englot B, Frewen TA, Sisson WM, Vladimirsky A (2015) A bi-criteria path planning algorithm for robotics applications. Preprint, submitted November 4, https://arxiv.org/abs/1511.01166.Google Scholar
• Cohen E, Halperin E, Kaplan H, Zwick U (2003) Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5):1338–1355.Crossref, Google Scholar
• Correa J, Harks T, Kreuzen VJC, Matuschke J (2017) Fare evasion in transit networks. Oper. Res. 65(1):165–183.Link, Google Scholar
• Demetrescu C, Goldberg AV, Johnson DS (2009) The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74. Demetrescu C, Goldberg AV, Johnson DS, eds. (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Disser Y, Feldmann AE, Klimm M, Könemann J (2019) Travelling on graphs with small highway dimension. Graph-Theoret. Concepts Comput. Sci. LNCS, 11789:175.Google Scholar
• Elkin M, Pettie S (2016) A linear-size logarithmic stretch path-reporting distance oracle for general graphs. ACM Trans. Algorithms 12(4):1–31.Crossref, Google Scholar
• Even G, Rawitz D, Shahar SM (2005) Hitting sets when the VC-dimension is small. Inform. Proc. Lett. 95(2):358–362.Crossref, Google Scholar
• Fan Y, Kalaba R, Moore J (2005) Arriving on time. J. Optim. Theory Appl. 127(3):497–513.Crossref, Google Scholar
• Feldmann AE (2019) Fixed-parameter approximations for k-center problems in low highway dimension graphs. Algorithmica 81(3):1031–1052.Crossref, Google Scholar
• Feldmann AE, Marx D (2018) The parameterized hardness of the k-center problem in transportation networks. 16th Scandinavian Sympos. Workshops Algorithm Theory (SWAT 2018) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik).Google Scholar
• Feldmann AE, Fung WS, Könemann J, Post I (2018) A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J. Comput. 47(4):1667–1704.Crossref, Google Scholar
• Festa P (2015) Constrained shortest path problems: state-of-the-art and recent advances. 2015 17th Intrnat. Conf. Transparent Optical Networks (ICTON), 1–17.Google Scholar
• Funke S, Nusser A, Storandt S (2014) On k-path covers and their applications. Proc. VLDB Endowment 7(10):893–902.Crossref, Google Scholar
• Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Internat. Workshop Experiment. Efficient Algorithms, (Springer, Berlin, Heidelberg).Google Scholar
• Hoy D, Nikolova E (2015) Approximately Optimal Risk-Averse Routing Policies Via Adaptive Discretization. Twenty-Ninth AAAI Conf. Artificial Intelligence (AAAI Publications), 29(1).Google Scholar
• Hunter T, Abbeel P, Bayen AM (2013) The Path Inference Filter: Model-Based Low-Latency Map Matching of Probe Vehicle Data (Algorithmic Foundations of Robotics X), (Springer, Berlin, Heidelberg), 1(1):591–607.Google Scholar
• Kosowski A, Viennot L (2017) Beyond highway dimension: Small distance labels using tree skeletons. Proc. Twenty-Eighth Annual ACM-SIAM Sympos. Discrete Algorithms, 1462–1478.Google Scholar
• Niknami M, Samaranayake S (2016) Tractable pathfinding for the stochastic on-time arrival problem. Internat. Sympos. Experiment. Algorithms, (Springer, Cham), 231–245.Google Scholar
• Nikolova E, Kelner JA, Brand M, Mitzenmacher M (2006) Stochastic shortest paths via quasi-convex maximization. Eur. Sympos. Algorithms, (Springer, Berlin, Heidelberg), 552–563.Google Scholar
• Rice M, Tsotras VJ (2010) Graph indexing of road networks for shortest path queries with label restrictions. Proc. VLDB Endowment 4(2):69–80.Crossref, Google Scholar
• Sabran G, Samaranayake S, Bayen A (2014) Precomputation techniques for the stochastic on-time arrival problem. 2014 Proc. Sixteenth Workshop Algortithm Engrg. Experiments (ALENEX), 138–146.Google Scholar
• White C (2015) Lower bounds in the preprocessing and query phases of routing algorithms. Algorithms-ESA (Springer), 1013–1024.Crossref, Google Scholar
• Woodard D, Nogin G, Koch P, Racz D, Goldszmidt M, Horvitz E (2017) Predicting travel time reliability using mobile phone gps data. Transportation Res. Part C: Emerging Tech. 75:30–44.Crossref, Google Scholar