{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:43Z","timestamp":1773481783005,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p>\n            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\n            <jats:italic>time-dependent graphs.<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/3339490.3339491","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:50:07Z","timestamp":1565182207000},"page":"1058-1070","source":"Crossref","is-referenced-by-count":30,"title":["Constrained shortest path query in a large time-dependent graph"],"prefix":"10.14778","volume":"12","author":[{"given":"Ye","family":"Yuan","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology"}]},{"given":"Xiang","family":"Lian","sequence":"additional","affiliation":[{"name":"Kent State University"}]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology"}]},{"given":"Yuliang","family":"Ma","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}]},{"given":"Yishu","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}]}],"member":"320","published-online":{"date-parts":[[2019,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/faculty.neu.edu.cn\/ise\/yuanye\/vldb2019full.pdf.  http:\/\/faculty.neu.edu.cn\/ise\/yuanye\/vldb2019full.pdf."},{"key":"e_1_2_1_2_1","unstructured":"Boundary of chengdu. https:\/\/www.openstreetmap.org\/node\/244077729.  Boundary of chengdu. https:\/\/www.openstreetmap.org\/node\/244077729."},{"key":"e_1_2_1_3_1","unstructured":"Didi chuxing. http:\/\/www.didichuxing.com\/.  Didi chuxing. http:\/\/www.didichuxing.com\/."},{"key":"e_1_2_1_4_1","unstructured":"Gaia. https:\/\/outreach.didichuxing.com\/research\/opendata\/.  Gaia. https:\/\/outreach.didichuxing.com\/research\/opendata\/."},{"key":"e_1_2_1_5_1","unstructured":"Osmconvert. https:\/\/wiki.openstreetmap.org\/wiki\/osmconvert.  Osmconvert. https:\/\/wiki.openstreetmap.org\/wiki\/osmconvert."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791220.2791230"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2003.12.019"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO;2-H"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90009-6"},{"key":"e_1_2_1_10_1","volume-title":"Continuous-time dynamics shortest path algorithms","author":"Brian C.","year":"1999","unstructured":"Dean and C. Brian . Continuous-time dynamics shortest path algorithms . Massachusetts Institute of Technology , 1999 . Dean and C. Brian. Continuous-time dynamics shortest path algorithms. Massachusetts Institute of Technology, 1999."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_28"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_2_1_13_1","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and intractability: a guide to the theory of NP-completeness . W.H.Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W.H.Freeman, 1979."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100403"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.1.36"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19488-6_126"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11753810_17"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137638"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00069-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00069-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647910.740331"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)E0349-G"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214078"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(77)90100-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1227166"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.07.017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9096-4"},{"key":"e_1_2_1_30_1","volume-title":"14th INFORMS Computing Society Conference","author":"Veneti A.","year":"2014","unstructured":"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 . 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."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816682"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749456"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732941"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00086"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3339490.3339491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:25:20Z","timestamp":1672223120000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3339490.3339491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":36,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.14778\/3339490.3339491"],"URL":"https:\/\/doi.org\/10.14778\/3339490.3339491","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}