{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T18:27:11Z","timestamp":1783535231440,"version":"3.55.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient or even flawed in a temporal graph, as the temporal information determines the order of activities along any path. In this paper, we show the shortcomings of classic shortest path in a temporal graph, and study various concepts of \"shortest\" path for temporal graphs. Computing these temporal paths is challenging as subpaths of a \"shortest\" path may not be \"shortest\" in a temporal graph. We investigate properties of the temporal paths and propose efficient algorithms to compute them. We tested our algorithms on real world temporal graphs to verify their efficiency, and also show that temporal paths are essential for studying temporal graphs by comparing shortest paths in normal static graphs.<\/jats:p>","DOI":"10.14778\/2732939.2732945","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"721-732","source":"Crossref","is-referenced-by-count":233,"title":["Path problems in temporal graphs"],"prefix":"10.14778","volume":"7","author":[{"given":"Huanhuan","family":"Wu","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silu","family":"Huang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yiping","family":"Ke","sequence":"additional","affiliation":[{"name":"Institute of High Performance Computing, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Lu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanyan","family":"Xu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213888"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0346-6"},{"key":"e_1_2_1_6_1","first-page":"228","volume-title":"SODA","author":"Eppstein D.","year":"2001","unstructured":"D. Eppstein and J. Wang . Fast approximation of centrality . In SODA , pages 228 -- 229 , 2001 . D. Eppstein and J. Wang. Fast approximation of centrality. In SODA, pages 228--229, 2001."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_8_1","volume-title":"Temporal networks. CoRR, abs\/1108.1780","author":"Holme P.","year":"2011","unstructured":"P. Holme and J. Saram\u00e4ki . Temporal networks. CoRR, abs\/1108.1780 , 2011 . P. Holme and J. Saram\u00e4ki. Temporal networks. CoRR, abs\/1108.1780, 2011."},{"key":"e_1_2_1_9_1","volume-title":"Temporal graph traversals: Definitions, algorithms, and applications. CoRR, abs\/1401.1919","author":"Huang S.","year":"2014","unstructured":"S. Huang , J. Cheng , and H. Wu . Temporal graph traversals: Definitions, algorithms, and applications. CoRR, abs\/1401.1919 , 2014 . S. Huang, J. Cheng, and H. Wu. Temporal graph traversals: Definitions, algorithms, and applications. CoRR, abs\/1401.1919, 2014."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1829"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401945"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2008.11.021"},{"key":"e_1_2_1_13_1","volume-title":"Components in time-varying graphs. CoRR, abs\/1106.2134","author":"Nicosia V.","year":"2011","unstructured":"V. Nicosia , J. Tang , M. Musolesi , G. Russo , C. Mascolo , and V. Latora . Components in time-varying graphs. CoRR, abs\/1106.2134 , 2011 . V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, and V. Latora. Components in time-varying graphs. CoRR, abs\/1106.2134, 2011."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.016105"},{"key":"e_1_2_1_15_1","volume-title":"Time-varying graphs and social network analysis: Temporal indicators and metrics. CoRR, abs\/1102.0629","author":"Santoro N.","year":"2011","unstructured":"N. Santoro , W. Quattrociocchi , P. Flocchini , A. Casteigts , and F. Amblard . Time-varying graphs and social network analysis: Temporal indicators and metrics. CoRR, abs\/1102.0629 , 2011 . N. Santoro, W. Quattrociocchi, P. Flocchini, A. Casteigts, and F. Amblard. Time-varying graphs and social network analysis: Temporal indicators and metrics. CoRR, abs\/1102.0629, 2011."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592674"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1672308.1672329"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.81.055101"},{"key":"e_1_2_1_19_1","volume-title":"Path problems in temporal graphs (preliminary version). www.cse.cuhk.edu.hk\/~hhwu\/temsp.pdf","author":"Wu H.","year":"2013","unstructured":"H. Wu , J. Cheng , S. Huang , Y. Ke , Y. Lu , and Y. Xu . Path problems in temporal graphs (preliminary version). www.cse.cuhk.edu.hk\/~hhwu\/temsp.pdf , 2013 . H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs (preliminary version). www.cse.cuhk.edu.hk\/~hhwu\/temsp.pdf, 2013."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835896"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001728"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732939.2732945","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:21:43Z","timestamp":1672222903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732939.2732945"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":21,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.14778\/2732939.2732945"],"URL":"https:\/\/doi.org\/10.14778\/2732939.2732945","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,5]]}}}