{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:20:03Z","timestamp":1767140403052,"version":"build-2238731810"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T00:00:00Z","timestamp":1695772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T00:00:00Z","timestamp":1695772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Innovation Capability Improvement Plan Project of Hebei Province","award":["22567626H"],"award-info":[{"award-number":["22567626H"]}]},{"name":"Innovation Capability Improvement Plan Project of Hebei Province","award":["22567626H"],"award-info":[{"award-number":["22567626H"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s10115-023-01958-8","type":"journal-article","created":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T16:27:04Z","timestamp":1695832024000},"page":"1135-1165","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Enumerating all multi-constrained s-t paths on temporal graph"],"prefix":"10.1007","volume":"66","author":[{"given":"Yue","family":"Jin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zijun","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenyuan","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,27]]},"reference":[{"issue":"3","key":"1958_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saram\u00e4ki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"key":"1958_CR2","doi-asserted-by":"crossref","unstructured":"Yue D, Wu X, Wang Y, Li Y, Chu C-H (2007) A review of data mining-based financial fraud detection research. In: Proceedings of the 2007 international conference on wireless communications, networking and mobile computing, pp 5519\u20135522","DOI":"10.1109\/WICOM.2007.1352"},{"issue":"Suppl.2","key":"1958_CR3","doi-asserted-by":"publisher","first-page":"ii33","DOI":"10.1093\/bioinformatics\/bti1105","volume":"21","author":"U Leser","year":"2005","unstructured":"Leser U (2005) A query language for biological networks. Bioinformatics 21(Suppl.2):ii33\u2013ii39","journal-title":"Bioinformatics"},{"key":"1958_CR4","doi-asserted-by":"crossref","unstructured":"Kimura M, Saito K (2006) Tractable models for information diffusion in social networks. In: Proceedings of the 10th European conference on principles and practice of knowledge discovery in databases, pp 259\u2013271","DOI":"10.1007\/11871637_27"},{"issue":"11","key":"1958_CR5","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.14778\/3236187.3236197","volume":"11","author":"R Kumar","year":"2018","unstructured":"Kumar R, Calders T (2018) 2SCENT: an efficient algorithm for enumerating all simple temporal cycles. Proc VLDB Endow 11(11):1441\u20131453","journal-title":"Proc VLDB Endow"},{"key":"1958_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"issue":"8","key":"1958_CR7","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1049\/el:19800212","volume":"16","author":"AA Khan","year":"1980","unstructured":"Khan AA, Singh H (1980) Petri net approach to enumerate all simple paths in a graph. Electron Lett 16(8):291\u2013292","journal-title":"Electron Lett"},{"key":"1958_CR8","doi-asserted-by":"crossref","unstructured":"Rizzi R, Sacomoto G, Sagot M-F (2014) Efficiently listing bounded length st-paths. In: Proceedings of the 25th international workshop on combinatorial algorithms, pp 318\u2013329","DOI":"10.1007\/978-3-319-19315-1_28"},{"key":"1958_CR9","doi-asserted-by":"crossref","unstructured":"Grossi R, Marino A, Versari L (2018) Efficient algorithms for listing k disjoint st-paths in graphs. In: Proceedings of the 13th Latin American symposium on theoretical informatics, pp 544\u2013557","DOI":"10.1007\/978-3-319-77404-6_40"},{"issue":"4","key":"1958_CR10","doi-asserted-by":"publisher","first-page":"463","DOI":"10.14778\/3372716.3372720","volume":"13","author":"Y Peng","year":"2019","unstructured":"Peng Y, Zhang Y, Lin X, Zhang W, Qin L, Zhou J (2019) Hop-constrained s\u2013t simple path enumeration: Towards bridging theory and practice. Proc VLDB Endow 13(4):463\u2013476","journal-title":"Proc VLDB Endow"},{"key":"1958_CR11","doi-asserted-by":"crossref","unstructured":"Lai Z, Peng Y, Yang S, Lin X, Zhang W (2021) PEFP: Efficient k-hop constrained s\u2013t simple path enumeration on FPGA. In: Proceedings of the 37th IEEE international conference on data engineering, pp 1320\u20131331","DOI":"10.1109\/ICDE51399.2021.00118"},{"key":"1958_CR12","doi-asserted-by":"crossref","unstructured":"Sun S, Chen Y, He B, Hooi B (2021) PathEnum: Towards real-time hop-constrained s\u2013t path enumeration. In: Proceedings of the 2021 international conference on management of data, pp 1758\u20131770","DOI":"10.1145\/3448016.3457290"},{"issue":"5","key":"1958_CR13","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1007\/s00778-021-00674-5","volume":"30","author":"Y Peng","year":"2021","unstructured":"Peng Y, Lin X, Zhang Y, Zhang W, Qin L, Zhou J (2021) Efficient hop-constrained s\u2013t simple path enumeration. VLDB J 30(5):799\u2013823","journal-title":"VLDB J"},{"issue":"2","key":"1958_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.14778\/3489496.3489499","volume":"15","author":"K Hao","year":"2021","unstructured":"Hao K, Yuan L, Zhang W (2021) Distributed hop-constrained s\u2013t simple path enumeration at billion scale. Proc VLDB Endow 15(2):169\u2013182","journal-title":"Proc VLDB Endow"},{"key":"1958_CR15","doi-asserted-by":"crossref","unstructured":"Li X, Hao K, Yang Z, Cao X, Zhang W, Yuan L, Lin X (2022) Hop-constrained s\u2013t simple path enumeration in billion-scale labelled graphs. In: Proceedings of the 23rd international conference on web information systems engineering, pp 49\u201364","DOI":"10.1007\/978-3-031-20891-1_5"},{"key":"1958_CR16","doi-asserted-by":"crossref","unstructured":"Li X, Hao K, Yang Z, Cao X, Zhang W (2022) Hop-constrained s\u2013t simple path enumeration in large uncertain graphs. In: Proceedings of the 33rd Australasian database conference on databases theory and applications, pp 115\u2013127","DOI":"10.1007\/978-3-031-15512-3_9"},{"key":"1958_CR17","doi-asserted-by":"crossref","unstructured":"Bu L, Xie Z, Lyu L, Li Y, Guo X, Zhao J, Li X (2022) BRICK:\u00a0Path\u00a0enumeration\u00a0based bounded reachability checking of C program (competition contribution). In: Proceedings of the 28th international conference on tools and algorithms for the construction and analysis of systems, Part II, pp 408\u2013412","DOI":"10.1007\/978-3-030-99527-0_22"},{"key":"1958_CR18","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Kumar A (2000) Connectivity and inference problems for temporal networks. In: Proceedings of the 32nd Annual ACM symposium on theory of computing, pp 504\u2013513","DOI":"10.1145\/335305.335364"},{"issue":"1","key":"1958_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson DB (1975) Finding all the elementary circuits of a directed graph. SIAM J Comput 4(1):77\u201384","journal-title":"SIAM J Comput"},{"key":"1958_CR20","doi-asserted-by":"crossref","unstructured":"Birmel\u00e9 E, Ferreira R, Grossi R, Marino A,  Pisanti N, Rizzi R,  Sacomoto G (2013) Optimal listing of cycles and st-paths in undirected graphs. In: Proceedings of the 24th Annual ACM-SIAM symposium on discrete algorithms, pp 1884\u20131896","DOI":"10.1137\/1.9781611973105.134"},{"key":"1958_CR21","doi-asserted-by":"crossref","unstructured":"Qing Z, Yuan L, Chen Z, Lin J, Ma G (2020) Efficient parallel cycle search in large graphs. In: Proceedings of the 25th international conference on database systems for advanced applications, Part II, pp 349\u2013367","DOI":"10.1007\/978-3-030-59416-9_21"},{"key":"1958_CR22","doi-asserted-by":"crossref","unstructured":"Blanu\u0161a J, Ienne P, Atasu K (2022) Scalable fine-grained parallel cycle enumeration algorithms. In: Proceedings of the 34th ACM symposium on parallelism in algorithms and architectures, pp 247\u2013258","DOI":"10.1145\/3490148.3538585"},{"issue":"4","key":"1958_CR23","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(83)90038-8","volume":"17","author":"O Shmueli","year":"1983","unstructured":"Shmueli O (1983) Dynamic cycle detection. Inf Process Lett 17(4):185\u2013188","journal-title":"Inf Process Lett"},{"key":"1958_CR24","doi-asserted-by":"crossref","unstructured":"Bernstein A, Chechik S (2018) Incremental topological sort and cycle detection in $$\\tilde{O}(m\\sqrt{{n}})$$ expected total time. In: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, pp 21\u201334","DOI":"10.1137\/1.9781611975031.2"},{"issue":"12","key":"1958_CR25","doi-asserted-by":"publisher","first-page":"1876","DOI":"10.14778\/3229863.3229874","volume":"11","author":"X Qiu","year":"2018","unstructured":"Qiu X, Cen W, Qian Z, Peng Y, Zhang Y, Lin X, Zhou J (2018) Real-time constrained cycle detection in large dynamic graphs. Proc VLDB Endow 11(12):1876\u20131888","journal-title":"Proc VLDB Endow"},{"key":"1958_CR26","first-page":"313","volume":"24(3)","author":"NP Khomenko","year":"1972","unstructured":"Khomenko NP, Golovko LD (1972) Identifying certain types of parts of a graph and computing their number. Ukr Math J 24(3):313\u2013321","journal-title":"Ukr Math J"},{"issue":"2","key":"1958_CR27","first-page":"1080","volume":"184","author":"GG Cash","year":"2007","unstructured":"Cash GG (2007) The number of n-cycles in a graph. Appl Math Comput 184(2):1080\u20131083","journal-title":"Appl Math Comput"},{"issue":"7","key":"1958_CR28","doi-asserted-by":"publisher","first-page":"2716","DOI":"10.1007\/s00453-019-00552-1","volume":"81","author":"P-L Giscard","year":"2019","unstructured":"Giscard P-L, Kriege N, Wilson RC (2019) A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica 81(7):2716\u20132737","journal-title":"Algorithmica"},{"issue":"2","key":"1958_CR29","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D Eppstein","year":"1998","unstructured":"Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28(2):652\u2013673","journal-title":"SIAM J Comput"},{"issue":"11","key":"1958_CR30","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"JY Yen","year":"1971","unstructured":"Yen JY (1971) Finding the k shortest loopless paths in a network. Manage Sci 17(11):712\u2013716","journal-title":"Manage Sci"},{"issue":"4","key":"1958_CR31","doi-asserted-by":"publisher","first-page":"45:1","DOI":"10.1145\/1290672.1290682","volume":"3","author":"J Hershberger","year":"2007","unstructured":"Hershberger J, Maxel M, Suri S (2007) Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans Algorithms 3(4):45:1-45:19","journal-title":"ACM Trans Algorithms"},{"issue":"7","key":"1958_CR32","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/j.ipl.2008.12.015","volume":"109","author":"Z Gotthilf","year":"2009","unstructured":"Gotthilf Z, Lewenstein M (2009) Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf Process Lett 109(7):352\u2013355","journal-title":"Inf Process Lett"},{"key":"1958_CR33","doi-asserted-by":"crossref","unstructured":"Gao J, Qiu H, Jiang X, Wang T, Yang D (2010) Fast top-k simple shortest paths discovery in graphs. In: Proceedings of the 19th ACM conference on information and knowledge management, pp 509\u2013518","DOI":"10.1145\/1871437.1871504"},{"key":"1958_CR34","unstructured":"Chang L, Lin X, Qin L, Yu JX, Pei J (2015) Efficiently computing top-k shortest path join. In: Proceedings of the 18th international conference on extending database technology, pp 133\u2013144"},{"key":"1958_CR35","doi-asserted-by":"crossref","unstructured":"Liu H, Jin C, Yang B, Zhou A (2018) Finding top-k shortest paths with diversity. In: Proceedings of the 34th IEEE international conference on data engineering, pp 1761\u20131762","DOI":"10.1109\/ICDE.2018.00238"},{"key":"1958_CR36","doi-asserted-by":"crossref","unstructured":"Zhu AD, Xiao X, Wang S, Lin W (2013) Efficient single-source shortest path and distance queries on large graphs. In: Proceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining, pp 998\u20131006","DOI":"10.1145\/2487575.2487665"},{"issue":"9","key":"1958_CR37","doi-asserted-by":"publisher","first-page":"721","DOI":"10.14778\/2732939.2732945","volume":"7","author":"H Wu","year":"2014","unstructured":"Wu H, Cheng J, Huang S, Ke Y, Lu Y, Xu Y (2014) Path problems in temporal graphs. Proc VLDB Endow 7(9):721\u2013732","journal-title":"Proc VLDB Endow"},{"key":"1958_CR38","doi-asserted-by":"crossref","unstructured":"Cao N, Fineman JT, Russell K (2021) Brief announcement: An improved distributed approximate single-source shortest paths algorithm. In: Proceedings of the 2021 ACM symposium on principles of distributed computing, virtual event, pp 493\u2013496","DOI":"10.1145\/3465084.3467945"},{"issue":"4","key":"1958_CR39","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1109\/TPDS.2021.3084096","volume":"33","author":"A Khanda","year":"2022","unstructured":"Khanda A, Srinivasan S, Bhowmick S, Norris B, Das SK (2022) A parallel algorithm template for updating single-source shortest paths in large-scale dynamic networks. IEEE Trans Parallel Distrib Syst 33(4):929\u2013940","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"1958_CR40","doi-asserted-by":"crossref","unstructured":"Costa MM, Silva MF (2019) A survey on path planning algorithms for mobile robots. In: Proceedings of 2019 IEEE international conference on autonomous robot systems and competitions, pp 1\u20137","DOI":"10.1109\/ICARSC.2019.8733623"},{"issue":"11","key":"1958_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3570723","volume":"55","author":"MR Jones","year":"2023","unstructured":"Jones M, Djahel S, Welsh K (2023) Path-planning for unmanned aerial vehicles with environment complexity considerations: a survey. ACM Comput Surv 55(11):234:1\u2013234:39","journal-title":"ACM Comput Surv"},{"issue":"3","key":"1958_CR42","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1007\/s10115-018-1297-4","volume":"60","author":"KH Lim","year":"2019","unstructured":"Lim KH, Chan J, Karunasekera S, Leckie C (2019) Tour recommendation and trip planning using location-based social media: a survey. Knowl Inf Syst 60(3):1247\u20131275","journal-title":"Knowl Inf Syst"},{"key":"1958_CR43","doi-asserted-by":"crossref","unstructured":"Hashem T, Ali ME (2017) Trip planning and scheduling queries in spatial databases: a survey. In: Proceedings of the 5th international conference on big data analytics, pp 164\u2013178","DOI":"10.1007\/978-3-319-72413-3_11"},{"issue":"5","key":"1958_CR44","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1002\/asi.21015","volume":"60","author":"P Panzarasa","year":"2009","unstructured":"Panzarasa P, Opsahl T, Carley KM (2009) Patterns and dynamics of users\u2019 behavior and interaction: Network analysis of an online community. J Am Soc Inform Sci Technol 60(5):911\u2013932","journal-title":"J Am Soc Inform Sci Technol"},{"key":"1958_CR45","doi-asserted-by":"crossref","unstructured":"Leskovec J, Huttenlocher D, Kleinberg J (2010) Governance in social media: A case study of the wikipedia promotion process. In: Proceedings of the 4th international conference on weblogs and social media, pp 98\u2013105","DOI":"10.1609\/icwsm.v4i1.14013"},{"key":"1958_CR46","doi-asserted-by":"crossref","unstructured":"Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: Proceedings of the 10th ACM international conference on web search and data mining, pp 601\u2013610","DOI":"10.1145\/3018661.3018731"},{"key":"1958_CR47","doi-asserted-by":"crossref","unstructured":"G\u00f3mez V, Kaltenbrunner A, L\u00f3pez V (2008) Statistical analysis of the social network and discussion threads in Slashdot. In: Proceedings of the 17th international conference on World Wide Web, pp 645\u2013654","DOI":"10.1145\/1367497.1367585"},{"key":"1958_CR48","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI conference on artificial intelligence, pp 4292\u20134293","DOI":"10.1609\/aaai.v29i1.9277"}],"updated-by":[{"DOI":"10.1007\/s10115-023-02026-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T00:00:00Z","timestamp":1706400000000}}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-023-01958-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-023-01958-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-023-01958-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,30]],"date-time":"2024-04-30T20:10:52Z","timestamp":1714507852000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-023-01958-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,27]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1958"],"URL":"https:\/\/doi.org\/10.1007\/s10115-023-01958-8","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,27]]},"assertion":[{"value":"1 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2024","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised to update error in the special character used in the article.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2024","order":8,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":9,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10115-023-02026-x","URL":"https:\/\/doi.org\/10.1007\/s10115-023-02026-x","order":11,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}