Ye Yuan
Xiang Lian
Abstract
The constrained shortest path (CSP) query over static graphs has been extensively studied, since it has wide applications in transportation networks, telecommunication networks and etc. Such networks are dynamic and evolve over time, being modeled as time-dependent graphs. Therefore, in this paper, we study the CSP query over a large time-dependent graph. Specifically, we study the point CSP (PCSP) query and interval CSP (ICSP) query. We formally prove that it is NP-complete to process a PCSP query and at least EXPSPACE to answer an ICSP query. We propose approximate sequential algorithms to answer the PCSP and ICSP queries efficiently. We also develop parallel algorithms for the queries that guarantee to scale with big time-dependent graphs. Using real-life graphs, we experimentally verify the efficiency and scalability of our algorithms.
- http://faculty.neu.edu.cn/ise/yuanye/vldb2019full.pdf.Google Scholar
- Boundary of chengdu. https://www.openstreetmap.org/node/244077729.Google Scholar
- Didi chuxing. http://www.didichuxing.com/.Google Scholar
- Gaia. https://outreach.didichuxing.com/research/opendata/.Google Scholar
- Osmconvert. https://wiki.openstreetmap.org/wiki/osmconvert.Google Scholar
- G. V. Batz, D. Delling, P. Sanders, and C. Vetter. Time-dependent contraction hierarchies. In Meeting on Algorithm Engineering & Expermiments, pages 97--105, 2009. Google ScholarDigital Library
- G. S. Brodal and R. Jacob. Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theoretical Computer Science, 92:3--15, 2004.Google ScholarCross Ref
- X. Cai, T. Kloks, and C. K. Wong. Time-varying shortest path problems. Networks, 29(3):141--150, 2015.Google ScholarCross Ref
- K. L. Cooke and E. Halsey. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis & Applications, 14(3):493--498, 1997.Google ScholarCross Ref
- Dean and C. Brian. Continuous-time dynamics shortest path algorithms. Massachusetts Institute of Technology, 1999.Google Scholar
- D. Delling. Time-dependent sharc-routing. In European Symposium on Algorithms, pages 332--343, 2008. Google ScholarDigital Library
- B. Ding, J. X. Yu, and L. Qin. Finding time-dependent shortest paths over large graphs. In EDBT, pages 205--216, 2008. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W.H.Freeman, 1979. Google ScholarDigital Library
- G. Y. Handler and I. Zang. A dual algorithm for the constrained shortest path problem. Networks, 10(4):293--309, 1980.Google ScholarCross Ref
- P. Hansen. Bicriterion path problems. Lecture Notes in Economics & Mathematical Systems, 177:109--127, 1980.Google ScholarCross Ref
- R. Hassin. Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 17(1):36--42, 1992.Google ScholarCross Ref
- C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. Springer Berlin Heidelberg, 1988.Google ScholarCross Ref
- F. Kuipers, A. Orda, D. Raz, and P. V. Mieghem. A comparison of exact and -approximation algorithms for constrained routing. In International Conference on Research in Networking, pages 197--208, 2006. Google ScholarDigital Library
- L. Li, W. Hua, X. Du, X. Zhou, L. Li, W. Hua, X. Du, and X. Zhou. Minimal on-road time route scheduling on time-dependent graphs. PVLDB, 10(11):1274--1285, 2017. Google ScholarDigital Library
- . D. H. Lorenz and D. R. Raz. A simple efficient approximation acheme for the restricted shortest path problem. In Operations Research Letters, pages 213--219, 1999. Google ScholarDigital Library
- D. H. Lorenz and D. Raz. A simple efficient approximation scheme for the restricted shortest path problem. Operations Research Letters, 28(5):213--219, 2001. Google ScholarDigital Library
- K. Mehlhorn and M. Ziegelmann. Resource constrained shortest paths. In European Symposium on Algorithms, pages 326--337, 2000. Google ScholarDigital Library
- K. Nachtigall. Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research, 83(1):154--166, 1995.Google ScholarCross Ref
- A. Orda and R. Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the Acm, 37(3):607--625, 1990. Google ScholarDigital Library
- C. S. Peskina. Numerical analysis of blood flow in the heart. Journal of Computational Physics, 25(3):220--252, 2015.Google ScholarCross Ref
- E. Pyrga, F. Schulz, D. Wagner, and C. Zaroliagis. Efficient models for timetable information in public transportation systems. Journal of Experimental Algorithmics, 12(1):2.4, 2008. Google ScholarDigital Library
- F. Schulz, D. Wagner, and K. Weihe. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. Journal of Experimental Algorithmics, 5(2):12, 2000. Google ScholarDigital Library
- O. J. Smith, N. Boland, and H. Waterer. Solving shortest path problems with a weight constraint and replenishment arcs. Computers & Operations Research, 39(5):964--984, 2012. Google ScholarDigital Library
- G. Tsaggouris and C. Zaroliagis. Multiobjective optimization: Improved fptas for shortest paths and non-linear objectives with applications. Theory of Computing Systems, 45(1):162--186, 2009. Google ScholarDigital Library
- A. Veneti, C. Konstantopoulos, and G. Pantziou. Continuous and discrete time label setting algorithms for the time dependent bi-criteria shortest path problem. In 14th INFORMS Computing Society Conference, 2014.Google Scholar
- L. Wang, Y. Xiao, B. Shao, and H. Wang. How to partition a billion-node graph. In ICDE, pages 568--579, 2014.Google ScholarCross Ref
- S. Wang, W. Lin, Y. Yang, X. Xiao, and S. Zhou. Efficient route planning on public transportation networks:a labelling approach. In ACM SIGMOD International Conference on Management of Data, pages 967--982, 2015. Google ScholarDigital Library
- H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs. PVLDB, 7(9):721--732, 2014. Google ScholarDigital Library
- H. Wu, Y. Huang, J. Cheng, J. Li, and Y. Ke. Reachability and time-based path queries in temporal graphs. In IEEE International Conference on Data Engineering, pages 145--156, 2016.Google ScholarCross Ref
- Y. Yang, H. Gao, J. X. Yu, and J. Li. Finding the cost-optimal path with time constraint over time-dependent graphs. PVLDB, 7(9):673--684, 2014. Google ScholarDigital Library
- Y. Yuan, X. Lian, G. Wang, L. Chen, Y. Ma, and Y. Wang. Weight-constrained route planning over time-dependent graphs. In 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8--11, 2019, pages 914--925, 2019.Google ScholarCross Ref
Recommendations
Learn to Optimize the Constrained Shortest Path on Large Dynamic Graphs
The constrained shortest path (<inline-formula><tex-math notation="LaTeX">$\mathtt {CSP}$</tex-math><alternatives><mml:math><mml:mi mathvariant="monospace">CSP</mml:mi></mml:math><inline-graphic xlink:href="rao-ieq1-3258974.gif"/></alternatives></inline-...
Top-K possible shortest path query over a large uncertain graph
WISE'11: Proceedings of the 12th international conference on Web information system engineeringThis paper studies the top-k possible shortest path (kSP) queries in a large uncertain graph, specifically, given two vertices S and T, a kSP query reports the top-k possible shortest paths from S to T. Different from existing solutions for uncertain ...
The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks
Finding Shortest Paths That Are Reliable and Satisfy Constraints on Time-Dependent Weights
Shortest path problems are used to model and solve a variety of real-world problems. In “The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks,” Ruß, Gust, and Neumann generalize multiple versions of the well-studied ...
The constrained reliable shortest path problem in stochastic time-dependent networks (CRSP-STD) extends the reliable, the time-dependent, and the constrained shortest path problem. In the CRSP-STD, shortest paths need to ensure on-time arrival with a ...
Comments