Efficient Algorithms for Temporal Path Computation
Huanhuan Wu, James Sheung-Chak Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, Hejun Wu · IEEE Transactions on Knowledge and Data Engineering · 2016
Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient. In this paper, we study various concepts of “shortest” path in temporal graphs, called minimum temporal paths. Computing these minimum temporal paths is challenging as subpaths of a “shortest” path may not be “shortest” in a temporal graph. We propose efficient algorithms to compute minimum temporal paths and verified their efficiency using large real-world temporal graphs.