{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T08:06:16Z","timestamp":1789200376870,"version":"build-2803163510"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T00:00:00Z","timestamp":1774569600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T00:00:00Z","timestamp":1774656000000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of Chin","doi-asserted-by":"crossref","award":["62302084"],"award-info":[{"award-number":["62302084"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of Chin","doi-asserted-by":"crossref","award":["U2441237"],"award-info":[{"award-number":["U2441237"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of Chin","doi-asserted-by":"crossref","award":["62402096"],"award-info":[{"award-number":["62402096"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Guangdong Basic and Applied Basic Research Foundation","award":["2023A1515110268"],"award-info":[{"award-number":["2023A1515110268"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of Chin","doi-asserted-by":"crossref","award":["61932004"],"award-info":[{"award-number":["61932004"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of Chin","doi-asserted-by":"crossref","award":["62225203"],"award-info":[{"award-number":["62225203"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of Chin","doi-asserted-by":"crossref","award":["U21A20516"],"award-info":[{"award-number":["U21A20516"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2026,9]]},"DOI":"10.1007\/s41019-026-00345-x","type":"journal-article","created":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:48:48Z","timestamp":1774626528000},"page":"616-635","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Label-Constrained Path Queries on Time-Dependent Graphs via LP-Tree Decomposition"],"prefix":"10.1007","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3373-7060","authenticated-orcid":false,"given":"Yishu","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinlong","family":"Chu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongjiao","family":"Sun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiangguo","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hangxu","family":"Ji","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,27]]},"reference":[{"key":"345_CR1","doi-asserted-by":"crossref","unstructured":"Dijkstra EW (2022) A note on two problems in connexion with graphs. In: Edsger Wybe Dijkstra: His Life, Work, and Legacy, pp. 287\u2013290","DOI":"10.1145\/3544585.3544600"},{"issue":"5","key":"345_CR2","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1016\/j.aej.2021.08.058","volume":"61","author":"D Di Caprio","year":"2022","unstructured":"Di Caprio D, Ebrahimnejad A, Alrezaamiri H, Santos-Arteaga FJ (2022) A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights. Alex Eng J 61(5):3403\u20133415","journal-title":"Alex Eng J"},{"issue":"12","key":"345_CR3","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.14778\/2732977.2732992","volume":"7","author":"H Wei","year":"2014","unstructured":"Wei H, Yu JX, Lu C, Jin R (2014) Reachability querying: an independent permutation labeling approach. Proc VLDB Endow 7(12):1191\u20131202","journal-title":"Proc VLDB Endow"},{"key":"345_CR4","volume":"121","author":"N Deo","year":"2020","unstructured":"Deo N, Strasser A, Wang H (2020) Temporal networks in logistics and transportation. Comput Oper Res 121:104976","journal-title":"Comput Oper Res"},{"key":"345_CR5","first-page":"203","volume":"108","author":"Y Liu","year":"2019","unstructured":"Liu Y, Bie Y, Wang Y (2019) Time-dependent constrained shortest path problems in urban transportation networks. Transp Res Part C Emerg Technol 108:203\u2013221","journal-title":"Transp Res Part C Emerg Technol"},{"issue":"2","key":"345_CR6","first-page":"1124","volume":"19","author":"W Chen","year":"2021","unstructured":"Chen W, Zhang L, Johnson SR (2021) Dynamic path optimization in pharmaceutical r&d networks. IEEE Trans Autom Sci Eng 19(2):1124\u20131136","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"345_CR7","unstructured":"Wang S, Kumar V, Rodriguez M (2022) Temporal graph algorithms for supply chain optimization. In: 2022 IEEE International Conference on Big Data, pp 2451\u20132460"},{"issue":"6","key":"345_CR8","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon AO, Wood PT (1995) Finding regular simple paths in graph databases. SIAM J Comput 24(6):1235\u20131258","journal-title":"SIAM J Comput"},{"issue":"3","key":"345_CR9","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C Barrett","year":"2000","unstructured":"Barrett C, Jacob R, Marathe M (2000) Formal-language-constrained path problems. SIAM J Comput 30(3):809\u2013837","journal-title":"SIAM J Comput"},{"key":"345_CR10","doi-asserted-by":"crossref","unstructured":"Barrett C, Bisset K, Jacob R, Konjevod G, Marathe M (2002) Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the transims router. In: European Symposium on Algorithms, pp 126\u2013138","DOI":"10.1007\/3-540-45749-6_15"},{"key":"345_CR11","doi-asserted-by":"crossref","unstructured":"Chowdhary K (2025) Minimization of finite automata. In: Theory of Computation: Automata, Formal Languages, Computation and Complexity, pp 129\u2013159","DOI":"10.1007\/978-981-97-6234-7_4"},{"key":"345_CR12","doi-asserted-by":"crossref","unstructured":"Barrett C, Bisset K, Holzer M, Konjevod G, Marathe M, Wagner D (2008) Engineering label-constrained shortest-path algorithms. In: International Conference on Algorithmic Applications in Management, pp 27\u201337","DOI":"10.1007\/978-3-540-68880-8_5"},{"key":"345_CR13","doi-asserted-by":"crossref","unstructured":"Delling D, Pajor T, Wagner D (2009) Accelerating multi-modal route planning by access-nodes. In: European Symposium on Algorithms, pp 587\u2013598","DOI":"10.1007\/978-3-642-04128-0_53"},{"key":"345_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2699886","volume":"19","author":"J Dibbelt","year":"2015","unstructured":"Dibbelt J, Pajor T, Wagner D (2015) User-constrained multimodal route planning. J Exp Algorithmics 19:1\u201319","journal-title":"J Exp Algorithmics"},{"issue":"2","key":"345_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.14778\/1921071.1921074","volume":"4","author":"M Rice","year":"2010","unstructured":"Rice M, Tsotras VJ (2010) Graph indexing of road networks for shortest path queries with label restrictions. Proc VLDB Endow 4(2):69\u201380","journal-title":"Proc VLDB Endow"},{"key":"345_CR16","unstructured":"Kirchler D, Liberti L, Pajor T, Wolfler\u00a0Calvo R (2011) Unialt for regular language constrained shortest paths on a multi-modal transportation network. In: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp 64\u201375"},{"key":"345_CR17","unstructured":"Bonchi F, Gionis A, Gullo F, Ukkonen A (2014) Distance oracles in edge-labeled graphs. In: EDBT, pp 547\u2013558"},{"key":"345_CR18","doi-asserted-by":"crossref","unstructured":"Likhyani A, Bedathur S (2013) Label constrained shortest path estimation. In: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, pp 1177\u20131180","DOI":"10.1145\/2505515.2507818"},{"issue":"3","key":"345_CR19","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s00778-022-00760-2","volume":"32","author":"Z Liu","year":"2023","unstructured":"Liu Z, Li L, Zhang M, Hua W, Zhou X (2023) Multi-constraint shortest path using forest hop labeling. VLDB J 32(3):595\u2013621","journal-title":"VLDB J"},{"key":"345_CR20","doi-asserted-by":"crossref","unstructured":"Feng B, Chen Z, Yuan L, Lin X, Wang L (2023) Contraction hierarchies with label restrictions maintenance in dynamic road networks. In: International Conference on Database Systems for Advanced Applications, pp 269\u2013285","DOI":"10.1007\/978-3-031-30675-4_18"},{"key":"345_CR21","doi-asserted-by":"crossref","unstructured":"Hassan MS, Aref WG, Aly AM (2016) Graph indexing for shortest-path finding over dynamic sub-graphs. In: Proceedings of the 2016 International Conference on Management of Data, pp 1183\u20131197","DOI":"10.1145\/2882903.2882933"},{"key":"345_CR22","doi-asserted-by":"crossref","unstructured":"Zhang U, Yuan L, Li W, Qin L, Zhang Y (2021) Efficient label-constrained shortest path queries on road networks: A tree decomposition approach. Proceedings of the VLDB Endowment","DOI":"10.14778\/3494124.3494148"},{"issue":"11","key":"345_CR23","doi-asserted-by":"publisher","first-page":"3082","DOI":"10.14778\/3681954.3681985","volume":"17","author":"L Wang","year":"2024","unstructured":"Wang L, Wong R-W (2024) Pcsp: efficiently answering label-constrained shortest path queries in road networks. Proc VLDB Endow 17(11):3082\u20133094","journal-title":"Proc VLDB Endow"},{"issue":"3","key":"345_CR24","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/0022-247X(66)90009-6","volume":"14","author":"KL Cooke","year":"1966","unstructured":"Cooke KL, Halsey E (1966) The shortest route through a network with time-dependent internodal transit times. J Math Anal Appl 14(3):493\u2013498","journal-title":"J Math Anal Appl"},{"key":"345_CR25","doi-asserted-by":"crossref","unstructured":"Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, pp 205\u2013216","DOI":"10.1145\/1353343.1353371"},{"issue":"1","key":"345_CR26","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/s00453-010-9461-6","volume":"62","author":"F Dehne","year":"2012","unstructured":"Dehne F, Omran MT, Sack J-R (2012) Shortest paths in time-dependent fifo networks. Algorithmica 62(1):416\u2013435","journal-title":"Algorithmica"},{"key":"345_CR27","doi-asserted-by":"crossref","unstructured":"Kanoulas E, Du Y, Xia T, Zhang D (2006) Finding fastest paths on a road network with speed patterns. In: 22nd International Conference on Data Engineering, pp 10\u201310","DOI":"10.1109\/ICDE.2006.71"},{"issue":"4","key":"345_CR28","first-page":"837","volume":"55","author":"R Gupta","year":"2021","unstructured":"Gupta R, Johansson F, Demiryurek U (2021) Time-dependent route planning in large-scale transportation networks. Transp Sci 55(4):837\u2013856","journal-title":"Transp Sci"},{"key":"345_CR29","unstructured":"Patel N, Williams J, Tanaka K (2020) Algorithmic approaches for time-dependent label-constrained routing. In: 2020 IEEE 36th International Conference on Data Engineering, pp 1573\u20131584"},{"issue":"1","key":"345_CR30","first-page":"336","volume":"298","author":"T Nguyen","year":"2022","unstructured":"Nguyen T, Chen X, Wang H (2022) Supply chain resilience with temporal path constraints. Eur J Oper Res 298(1):336\u2013351","journal-title":"Eur J Oper Res"},{"issue":"8","key":"345_CR31","first-page":"3984","volume":"61","author":"M Rodriguez","year":"2021","unstructured":"Rodriguez M, Schmidt D, Zhang W (2021) Chemical reaction network optimization with temporal constraints. J Chem Inf Model 61(8):3984\u20133995","journal-title":"J Chem Inf Model"},{"issue":"6","key":"345_CR32","first-page":"6125","volume":"35","author":"X Li","year":"2023","unstructured":"Li X, Johnson B, Wang C (2023) Deep learning for time-dependent constrained path planning. IEEE Trans Knowl Data Eng 35(6):6125\u20136139","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"345_CR33","doi-asserted-by":"crossref","unstructured":"Yang B, Guo C, Jensen CS, Kaul M, Shang S (2014) Stochastic skyline route planning under time-varying uncertainty, pp 136\u2013147","DOI":"10.1109\/ICDE.2014.6816646"},{"issue":"2","key":"345_CR34","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1002\/net.20438","volume":"59","author":"G Nannicini","year":"2012","unstructured":"Nannicini G, Delling D, Schultes D, Liberti L (2012) Bidirectional a* search on time-dependent road networks. Networks 59(2):240\u2013251","journal-title":"Networks"},{"key":"345_CR35","doi-asserted-by":"crossref","unstructured":"Demiryurek U, Banaei-Kashani F, Shahabi C, Ranganathan A (2011) Online computation of fastest path in time-dependent spatial networks. In: International Symposium on Spatial and Temporal Databases, pp 92\u2013111","DOI":"10.1007\/978-3-642-22922-0_7"},{"issue":"1","key":"345_CR36","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00453-009-9341-0","volume":"60","author":"D Delling","year":"2011","unstructured":"Delling D (2011) Time-dependent sharc-routing. Algorithmica 60(1):60\u201394","journal-title":"Algorithmica"},{"issue":"11","key":"345_CR37","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.14778\/3342263.3342265","volume":"12","author":"Y Wang","year":"2019","unstructured":"Wang Y, Li G, Tang N (2019) Querying shortest paths on time dependent road networks. Proc VLDB Endow 12(11):1249\u20131261","journal-title":"Proc VLDB Endow"},{"key":"345_CR38","doi-asserted-by":"crossref","unstructured":"Li K, Chen L, Shang S (2021) Towards alleviating traffic congestion: Optimal route planning for massive-scale trips, pp 3400\u20133406","DOI":"10.24963\/ijcai.2020\/470"},{"key":"345_CR39","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.neucom.2016.02.085","volume":"213","author":"S Shang","year":"2016","unstructured":"Shang S, Guo D, Liu J, Wen J-R (2016) Prediction-based unobstructed route planning. Neurocomputing 213:147\u2013154","journal-title":"Neurocomputing"},{"key":"345_CR40","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2025.114242","volume":"329","author":"L Ding","year":"2025","unstructured":"Ding L, Han Y, Li M, Cui N, Wang X, Borovica-Gajic R (2025) Adaptive anchor-based attention networks for large-scale sparse bipartite graph embedding. Knowl Based Syst 329:114242","journal-title":"Knowl Based Syst"},{"key":"345_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2024.111961","volume":"297","author":"M Li","year":"2024","unstructured":"Li M, Borovica-Gajic R, Choudhury FM, Cui N, Ding L (2024) Maximal size constraint community search over bipartite graphs. Knowl Based Syst 297:111961","journal-title":"Knowl Based Syst"},{"issue":"3","key":"345_CR42","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender HL, Koster AMCA (2010) Treewidth computations I. upper bounds. Inf Comput 208(3):259\u2013275","journal-title":"Inf Comput"},{"key":"345_CR43","unstructured":"https:\/\/snap.stanford.edu\/data\/index.html"},{"key":"345_CR44","doi-asserted-by":"crossref","unstructured":"Gong Z, Zeng Y, Chen L (2023) Querying Shortest Path on Large Time-Dependent Road Networks with Shortcuts (arXiv:2303.03720)","DOI":"10.1109\/ICDE60146.2024.00345"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-026-00345-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-026-00345-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-026-00345-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T07:19:34Z","timestamp":1789197574000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-026-00345-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,27]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["345"],"URL":"https:\/\/doi.org\/10.1007\/s41019-026-00345-x","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,27]]},"assertion":[{"value":"16 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","label":"Ethics approval and consent to participate","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Approval","order":3,"name":"Ethics","label":"Consent for publication","group":{"name":"EthicsHeading","label":"Declarations"}}]}}