{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T11:09:59Z","timestamp":1778238599362,"version":"3.51.4"},"reference-count":73,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T00:00:00Z","timestamp":1778198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T00:00:00Z","timestamp":1778198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1007\/s00778-026-00977-5","type":"journal-article","created":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T10:18:06Z","timestamp":1778235486000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficiently querying connected components in large temporal graphs via scalable and maintainable indices"],"prefix":"10.1007","volume":"35","author":[{"given":"Yuyang","family":"Xia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haoxuan","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wensheng","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong","family":"Wen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,8]]},"reference":[{"key":"977_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Sheng, C., Tao, Y., Wilkinson, B.T.: Concurrent range reporting in two-dimensional space. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete algorithms 983\u2013994 . SIAM, (2014)","DOI":"10.1137\/1.9781611973402.73"},{"issue":"02","key":"977_CR2","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1142\/S0129626419500099","volume":"29","author":"EC Akrida","year":"2019","unstructured":"Akrida, E.C., Spirakis, P.G.: On verifying and maintaining connectivity of interval temporal networks. Parallel Processing Letters 29(02), 142\u2013154 (2019)","journal-title":"Parallel Processing Letters"},{"key":"977_CR3","doi-asserted-by":"crossref","unstructured":"Allard, G., Jacquet, P., Mans, B.: Routing in extremely mobile networks. In K. Al Agha, I. Gu\u00e9rin Lassous, and G. Pujolle, editors, Challenges in Ad Hoc Networking 129\u2013138 (2006)","DOI":"10.1007\/0-387-31173-4_15"},{"issue":"10","key":"977_CR4","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"36","author":"B Awerbuch","year":"1987","unstructured":"Awerbuch, B., Shiloach, Y.: New connectivity and msf algorithms for shuffle-exchange network and pram. IEEE Trans. Comput. 36(10), 1258\u20131263 (1987)","journal-title":"IEEE Trans. Comput."},{"key":"977_CR5","doi-asserted-by":"crossref","unstructured":"Beamer, S., Bulu\u00e7, A., Asanovic, K., Patterson, D.: Distributed memory breadth-first search revisited: Enabling bottom-up search. In 2013 IEEE International Symposium on Parallel and Distributed Processing. Workshops and Phd Forum 1618\u20131627 (2013)","DOI":"10.1109\/IPDPSW.2013.159"},{"key":"977_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Probst, M., Wulff-Nilsen, C.: Decremental strongly-connected components and single-source reachability in near-linear time. In ACM SIGACT 365\u2013376 (2019)","DOI":"10.1145\/3313276.3316335"},{"key":"977_CR7","doi-asserted-by":"crossref","unstructured":"Bhadra, S., Ferreira, A.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Samuel Pierre, Michel Barbeau, and Evangelos Kranakis, editors, Ad-Hoc, Mobile, and Wireless Networks 259\u2013270 (2003)","DOI":"10.1007\/978-3-540-39611-6_23"},{"issue":"3","key":"977_CR8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s13174-012-0073-z","volume":"3","author":"S Bhadra","year":"2012","unstructured":"Bhadra, S., Ferreira, A.: Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs. Journal of Internet Services and Applications 3(3), 269\u2013275 (2012)","journal-title":"Journal of Internet Services and Applications"},{"key":"977_CR9","doi-asserted-by":"crossref","unstructured":"Cai, T., Cheng, D., Liang, C., Liu, Z., Gu, L., Xie, H., Zhang, Z., Zeng, X., Gu, J.: Linklouvain: Link-aware a\/b testing and its application on online marketing campaign. In Christian\u00a0S. Jensen, Ee-Peng Lim, De-Nian Yang, Wang-Chien Lee, Vincent\u00a0S. Tseng, Vana Kalogeraki, Jen-Wei Huang, and Chih-Ya Shen, editors, Database Systems for Advanced Applications, pages 499\u2013510, Cham, Springer International Publishing. ISBN 978-3-030-73200-4 (2021)","DOI":"10.1007\/978-3-030-73200-4_34"},{"key":"977_CR10","doi-asserted-by":"publisher","unstructured":"cGregor, A.M.: Graph stream algorithms: A survey. SIGMOD Rec., 43 (1): 9\u201320, (2014) ISSN 0163-580 https:\/\/doi.org\/10.1145\/2627692.2627694","DOI":"10.1145\/2627692.2627694"},{"key":"977_CR11","doi-asserted-by":"publisher","unstructured":"Chen, X., Wang, K., Lin, X., Wenjie Zhang, L., Qin, Ying, Z.: Efficiently answering reachability and path queries on temporal bipartite graphs. Proc. VLDB Endow. 14(10), 1845\u20131858 (2021a). https:\/\/doi.org\/10.14778\/3467861.3467873","DOI":"10.14778\/3467861.3467873"},{"key":"977_CR12","doi-asserted-by":"publisher","unstructured":"Chen, X., Wang, K., Lin, X., Wenjie Zhang, L., Qin, Zhang, Y.: Efficiently answering reachability and path queries on temporal bipartite graphs. Proc. VLDB Endow. 14(10), 1845\u20131858 (2021). https:\/\/doi.org\/10.14778\/3467861.3467873","DOI":"10.14778\/3467861.3467873"},{"key":"977_CR13","doi-asserted-by":"crossref","unstructured":"Chowdhury, A., Rahman, J.S., Hawlader, M.S.: Well-connectedness - a novel measure for improving protein complex detection from ppi network. In 2016 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), 1\u20136 (2016)","DOI":"10.1109\/CIBCB.2016.7758105"},{"key":"977_CR14","doi-asserted-by":"crossref","unstructured":"Crouch, M.S., McGregor, A., Stubbs, D.: Dynamic graphs in the sliding-window model. In Hans\u00a0L. Bodlaender and Giuseppe\u00a0F. Italiano, editors, Algorithms \u2013 ESA 2013, pages 337\u2013348, Berlin, Heidelberg, Springer Berlin Heidelberg. ISBN 978-3-642-40450-4 (2013)","DOI":"10.1007\/978-3-642-40450-4_29"},{"issue":"5","key":"977_CR15","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/BF01383882","volume":"17","author":"G Cybenko","year":"1989","unstructured":"Cybenko, G., Allen, T.G., Polito, J.E.: Practical parallel union-find algorithms for transitive closure and clustering. Int. J. Parallel Program. 17(5), 403\u2013423 (1989)","journal-title":"Int. J. Parallel Program."},{"issue":"3","key":"977_CR16","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"Daniel Dominic Sleator and Robert Endre Tarjan","year":"1985","unstructured":"Daniel Dominic Sleator and Robert Endre Tarjan: Self-adjusting binary search trees. Journal of the ACM (JACM) 32(3), 652\u2013686 (1985)","journal-title":"Journal of the ACM (JACM)"},{"key":"977_CR17","doi-asserted-by":"crossref","unstructured":"Erling, O., Averbuch, A., Larriba-Pey, J., Chafi, H., Gubichev, A., Prat, A., Pham, M.-D., Boncz, P.: The ldbc social network benchmark: Interactive workload. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, 619\u2013630 (2015)","DOI":"10.1145\/2723372.2742786"},{"key":"977_CR18","doi-asserted-by":"publisher","unstructured":"Fabijan, A., Dmitriev, P., Olsson, H.H., Bosch, J.: Online controlled experimentation at scale: An empirical survey on the current state of a\/b testing. In 2018 44th Euromicro Conference on Software Engineering and Advanced Applications (SEAA), 68\u201372, (2018) https:\/\/doi.org\/10.1109\/SEAA.2018.00021","DOI":"10.1109\/SEAA.2018.00021"},{"key":"977_CR19","doi-asserted-by":"publisher","unstructured":"Fan, W., Tian, C.: Incremental graph computations: Doable and undoable. ACM Trans. Database Syst. 47(2) (2022). https:\/\/doi.org\/10.1145\/3500930","DOI":"10.1145\/3500930"},{"issue":"1","key":"977_CR20","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00778-019-00556-x","volume":"29","author":"Y Fang","year":"2020","unstructured":"Fang, Y., Xin Huang, L., Qin, Y.Z., Zhang, W., Cheng, R., Lin, X.: A survey of community search over big graphs. VLDB J. 29(1), 353\u2013392 (2020)","journal-title":"VLDB J."},{"key":"977_CR21","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6, and Donald Sannella, editors, Automata, Languages and Programming, pages 531\u2013543, Berlin, Heidelberg, Springer Berlin Heidelberg. ISBN 978-3-540-27836-8 (2004)","DOI":"10.1007\/978-3-540-27836-8_46"},{"key":"977_CR22","doi-asserted-by":"crossref","unstructured":"Feng, X., Chang, L., Lin, X., Qin, L., Zhang, W.: Computing connected components with linear communication cost in pregel-like systems. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 85\u201396. IEEE, (2016)","DOI":"10.1109\/ICDE.2016.7498231"},{"key":"977_CR23","doi-asserted-by":"crossref","unstructured":"Fleischer, L.K.: Bruce Hendrickson, and Ali P\u0131nar. On identifying strongly connected components in parallel. In International Parallel and Distributed Processing Symposium, pages 505\u2013511. Springer, (2000)","DOI":"10.1007\/3-540-45591-4_68"},{"issue":"8","key":"977_CR24","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1093\/bioinformatics\/btr099","volume":"27","author":"AD Fox","year":"2011","unstructured":"Fox, A.D., Hescott, B.J., Blumer, A.C., Slonim, D.K.: Connectedness of PPI network neighborhoods identifies regulatory hub proteins. Bioinformatics 27(8), 1135\u20131142 (2011)","journal-title":"Bioinformatics"},{"key":"977_CR25","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees. In Proceedings of the fifteenth annual ACM symposium on Theory of computing 252\u2013257 (1983)","DOI":"10.1145\/800061.808754"},{"issue":"3","key":"977_CR26","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(00)00051-X","volume":"74","author":"HN Gabow","year":"2000","unstructured":"Gabow, H.N.: Path-based depth-first search for strong and biconnected components. Inf. Process. Lett. 74(3), 107\u2013114 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"977_CR27","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/0207024","volume":"7","author":"HN Gabow","year":"1978","unstructured":"Gabow, H.N., Myers, E.W.: Finding all spanning trees of directed and undirected graphs. SIAM J. Comput. 7(3), 280\u2013287 (1978)","journal-title":"SIAM J. Comput."},{"key":"977_CR28","doi-asserted-by":"crossref","unstructured":"Graefe, G., Ward, K.: Dynamic query evaluation plans. In Proceedings of the 1989 ACM SIGMOD international conference on Management of data, 358\u2013366 (1989)","DOI":"10.1145\/67544.66960"},{"key":"977_CR29","doi-asserted-by":"publisher","unstructured":"Gui, H., Xu, Y., Bhasin, A., Han, J.: Network a\/b testing: From sampling to estimation. In Proceedings of the 24th International Conference on World Wide Web, WWW \u201915, page 399\u2013409, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee. ISBN 978145033469https:\/\/doi.org\/10.1145\/2736277.2741081","DOI":"10.1145\/2736277.2741081"},{"key":"977_CR30","doi-asserted-by":"crossref","unstructured":"Gurukar, S., Ranu, S., Ravindran, B.: Commit: A scalable approach to mining communication motifs from dynamic networks. In SIGMOD 475\u2013489 (2015)","DOI":"10.1145\/2723372.2737791"},{"key":"977_CR31","doi-asserted-by":"crossref","unstructured":"Haryan, C.A., Ramakrishna, G., Kothapalli, K., Banerjee, D.S.: Shared-memory parallel algorithms for fully dynamic maintenance of 2-connected components. In IPDPS, pages 1195\u20131205. IEEE, (2022)","DOI":"10.1109\/IPDPS53621.2022.00119"},{"key":"977_CR32","doi-asserted-by":"crossref","unstructured":"Hong, S., Rodia, N.C., Olukotun, K.: On fast parallel detection of strongly connected components (scc) in small-world graphs. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pages 1\u201311, (2013)","DOI":"10.1145\/2503210.2503246"},{"key":"977_CR33","doi-asserted-by":"crossref","unstructured":"Huang, S.-E., Huang, D., Kopelowitz, T., Pettie, S.: Fully dynamic connectivity in o (log n (log log n) 2) amortized expected time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms 510\u2013520 (2017)","DOI":"10.1137\/1.9781611974782.32"},{"issue":"9","key":"977_CR34","doi-asserted-by":"publisher","first-page":"721","DOI":"10.14778\/2732939.2732945","volume":"7","author":"W Huanhuan","year":"2014","unstructured":"Huanhuan, W., Cheng, J., Huang, S., Ke, Y., Yi, L., Yanyan, X.: Path problems in temporal graphs. Proceedings of the VLDB Endowment 7(9), 721\u2013732 (2014)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"977_CR35","doi-asserted-by":"crossref","unstructured":"Jacquet, P., Mans, B.: Routing in intermittently connected networks: Age rumors in connected components. In Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerComW\u201907), pages 53\u201358, (2007)","DOI":"10.1109\/PERCOMW.2007.101"},{"key":"977_CR36","doi-asserted-by":"crossref","unstructured":"Ji, Y., Liu, H., Howie, H., Huang.: ispan: Parallel identification of strongly connected components with spanning trees. In SC18: International Conference for High Performance Computing. Networking, Storage and Analysis 731\u2013742 . IEEE, (2018)","DOI":"10.1109\/SC.2018.00061"},{"key":"977_CR37","doi-asserted-by":"crossref","unstructured":"Khurana, U., Deshpande, A.: Efficient snapshot retrieval over historical graph data. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 997\u20131008, (2013)","DOI":"10.1109\/ICDE.2013.6544892"},{"issue":"4","key":"977_CR38","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1007\/s00453-015-0003-0","volume":"74","author":"S Kontogiannis","year":"2016","unstructured":"Kontogiannis, S., Zaroliagis, C.: Distance oracles for time-dependent networks. Algorithmica 74(4), 1404\u20131434 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0003-0","journal-title":"Algorithmica"},{"key":"977_CR39","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: KONECT - The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion 1343\u20131350 (2013)","DOI":"10.1145\/2487788.2488173"},{"issue":"3","key":"977_CR40","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1162\/0024389054396890","volume":"36","author":"M Kural","year":"2005","unstructured":"Kural, M.: Tree traversal and word order. Linguistic Inquiry 36(3), 367\u2013387 (2005)","journal-title":"Linguistic Inquiry"},{"issue":"6","key":"977_CR41","first-page":"1","volume":"2","author":"X Lantian","year":"2024","unstructured":"Lantian, X., Dong Wen, L., Qin, R.L., Zhang, Y., Lin, X.: Constant-time connectivity querying in dynamic graphs. Proceedings of the ACM on Management of Data 2(6), 1\u201323 (2024)","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"977_CR42","unstructured":"Leiserson, C.E., Rivest, R.L., Cormen, T.H., Stein, C.: Introduction to algorithms, volume\u00a03. MIT press, (1994)"},{"issue":"1","key":"977_CR43","first-page":"1","volume":"8","author":"J Leskovec","year":"2016","unstructured":"Leskovec, J., Sosi\u010d, R.: Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST) 8(1), 1 (2016)","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"key":"977_CR44","doi-asserted-by":"crossref","unstructured":"Levorato, V., Petermann, C.: Detection of communities in directed networks based on strongly p-connected components. 10 (2011)","DOI":"10.1109\/CASON.2011.6085946"},{"key":"977_CR45","doi-asserted-by":"crossref","unstructured":"Li, R.-H., Su, J., Qin, L., Yu, J.X., Dai, Q.: Persistent community search in temporal networks. In ICDE, pages 797\u2013808. IEEE,(2018)","DOI":"10.1109\/ICDE.2018.00077"},{"issue":"1","key":"977_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.sysarc.2013.10.014","volume":"60","author":"G Li","year":"2014","unstructured":"Li, G., Zhu, Z., Cong, Z., Yang, F.: Efficient decomposition of strongly connected components on gpus. J. Syst. Architect. 60(1), 1\u201310 (2014)","journal-title":"J. Syst. Architect."},{"issue":"2","key":"977_CR47","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10009-015-0382-1","volume":"18","author":"G Lowe","year":"2016","unstructured":"Lowe, G.: Concurrent depth-first search algorithms based on tarjan\u2019s algorithm. Int. J. Softw. Tools Technol. Transfer 18(2), 129\u2013147 (2016)","journal-title":"Int. J. Softw. Tools Technol. Transfer"},{"key":"977_CR48","doi-asserted-by":"crossref","unstructured":"Ma, S., Hu, R., Wang, L., Lin, X., Huai, J.: Fast computation of dense temporal subgraphs. In ICDE, pages 361\u2013372. IEEE, (2017)","DOI":"10.1109\/ICDE.2017.95"},{"key":"977_CR49","unstructured":"Madnick, S.E., Infoplex, M.H.: research in a high-performance database computer. (1986)"},{"key":"977_CR50","doi-asserted-by":"crossref","unstructured":"Manne, F., Patwary, Md. M.A.: A scalable parallel union-find algorithm for distributed memory computers. pages 186\u2013195, 09 (2009). ISBN 978-3-642-14389-2","DOI":"10.1007\/978-3-642-14390-8_20"},{"issue":"2","key":"977_CR51","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"EM McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257\u2013276 (1985)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"977_CR52","doi-asserted-by":"publisher","first-page":"2033","DOI":"10.14778\/3476249.3476260","volume":"14","author":"Yu Michael","year":"2021","unstructured":"Michael, Yu., Dong Wen, L., Qin, Y.Z., Zhang, W., Lin, X.: On querying historical k-cores. Proc. VLDB Endow. 14(11), 2033\u20132045 (2021)","journal-title":"Proc. VLDB Endow."},{"key":"977_CR53","doi-asserted-by":"publisher","unstructured":"Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12, 03 201https:\/\/doi.org\/10.1007\/978-3-319-24024-4_18","DOI":"10.1007\/978-3-319-24024-4_18"},{"key":"977_CR54","doi-asserted-by":"crossref","unstructured":"Qin, L., Yu, J.X., Chang, L., Cheng, H., Zhang, C., Lin, X.: Scalable big graph processing in mapreduce. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 827\u2013838, (2014)","DOI":"10.1145\/2588555.2593661"},{"issue":"12","key":"977_CR55","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.: Real-time constrained cycle detection in large dynamic graphs. Proceedings of the VLDB Endowment 11(12), 1876\u20131888 (2018)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"977_CR56","doi-asserted-by":"crossref","unstructured":"Rannou, L., Magnien, C., Latapy, M.: Strongly connected components in stream graphs: Computation and experimentations. In International Conference on Complex Networks and Their Applications, pages 568\u2013580. Springer, (2020)","DOI":"10.1007\/978-3-030-65347-7_47"},{"key":"977_CR57","doi-asserted-by":"crossref","unstructured":"Rastogi, V., Machanavajjhala, A., Chitnis, L., Sarma, A.D.: Finding connected components in map-reduce in logarithmic rounds. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 50\u201361. IEEE, (2013)","DOI":"10.1109\/ICDE.2013.6544813"},{"issue":"5","key":"977_CR58","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"JH Reif","year":"1985","unstructured":"Reif, J.H.: Depth-first search is inherently sequential. Inf. Process. Lett. 20(5), 229\u2013234 (1985)","journal-title":"Inf. Process. Lett."},{"key":"977_CR59","doi-asserted-by":"crossref","unstructured":"Salihoglu, S., Widom, J.: Optimizing graph algorithms on pregel-like systems. Proceedings of the VLDB Endowment 7(7) (2014)","DOI":"10.14778\/2732286.2732294"},{"issue":"1","key":"977_CR60","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0898-1221(81)90008-0","volume":"7","author":"M Sharir","year":"1981","unstructured":"Sharir, M.: A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications 7(1), 67\u201372 (1981)","journal-title":"Computers & Mathematics with Applications"},{"key":"977_CR61","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. In Proceedings of the thirteenth annual ACM symposium on Theory of computing 114\u2013122 (1981)","DOI":"10.1145\/800076.802464"},{"key":"977_CR62","doi-asserted-by":"crossref","unstructured":"Slota, G.M., Rajamanickam, S., Madduri, K.: Bfs and coloring-based parallel algorithms for strongly connected components and related problems. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pages 550\u2013559. IEEE, (2014)","DOI":"10.1109\/IPDPS.2014.64"},{"issue":"3","key":"977_CR63","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3654960","volume":"2","author":"J Song","year":"2024","unstructured":"Song, J., Wen, D., Lantian, X., Qin, L., Zhang, W., Lin, X.: On querying historical connectivity in temporal graphs. Proceedings of the ACM on Management of Data 2(3), 1\u201325 (2024)","journal-title":"Proceedings of the ACM on Management of Data"},{"issue":"2","key":"977_CR64","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"977_CR65","doi-asserted-by":"crossref","unstructured":"Tench, D., West, E., Zhang, V., Bender, M.A., Chowdhury, A., Dellas, J.A., Farach-Colton, M., Seip, T., Zhang, K.: Graphzeppelin: Storage-friendly sketching for connected components on dynamic graph streams. In SIGMOD, pages 325\u2013339. ACM, (2022)","DOI":"10.1145\/3514221.3526146"},{"key":"977_CR66","doi-asserted-by":"crossref","unstructured":"Vernet, M., Pign\u00e9, Y., Sanlaville, E.: A study of connectivity on dynamic graphs: computing persistent connected components. 4OR, 04 (2022)","DOI":"10.1007\/s10288-022-00507-3"},{"key":"977_CR67","doi-asserted-by":"crossref","unstructured":"Wen, D., Huang, Y., Zhang, Y., Qin, L., Zhang, W., Lin, X.: Efficiently answering span-reachability queries in large temporal graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), 1153\u20131164, (2020)","DOI":"10.1109\/ICDE48307.2020.00104"},{"issue":"4","key":"977_CR68","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/s00778-021-00715-z","volume":"31","author":"D Wen","year":"2022","unstructured":"Wen, D., Yang, B., Ying Zhang, L., Qin, D.C., Zhang, W.: Span-reachability querying in large temporal graphs. VLDB J. 31(4), 629\u2013647 (2022)","journal-title":"VLDB J."},{"issue":"3","key":"977_CR69","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/s10703-016-0246-7","volume":"48","author":"A Wijs","year":"2016","unstructured":"Wijs, A., Katoen, J.-P., Bo\u0161na\u010dki, D.: Efficient gpu algorithms for parallel decomposition of graphs into strongly connected and maximal end components. Formal Methods in System Design 48(3), 274\u2013300 (2016)","journal-title":"Formal Methods in System Design"},{"key":"977_CR70","doi-asserted-by":"crossref","unstructured":"Wu, H., Cheng, J., Lu, Y., Ke, Y., Huang, Y., Yan, D., Wu, H.: Core decomposition in large temporal graphs. In 2015 IEEE International Conference on Big Data (Big Data), pages 649\u2013658. IEEE, (2015)","DOI":"10.1109\/BigData.2015.7363809"},{"issue":"2","key":"977_CR71","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3589315","volume":"1","author":"H Xie","year":"2023","unstructured":"Xie, H., Fang, Y., Xia, Y., Luo, W., Ma, C.: On querying connected components in large temporal graphs. Proceedings of the ACM on Management of Data 1(2), 1\u201327 (2023)","journal-title":"Proceedings of the ACM on Management of Data"},{"issue":"14","key":"977_CR72","doi-asserted-by":"publisher","first-page":"1821","DOI":"10.14778\/2733085.2733089","volume":"7","author":"D Yan","year":"2014","unstructured":"Yan, D., Cheng, J., Xing, K., Yi, L., Ng, W., Yingyi, B.: Pregel algorithms for graph connectivity problems with performance guarantees. Proceedings of the VLDB Endowment 7(14), 1821\u20131832 (2014)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"977_CR73","doi-asserted-by":"crossref","unstructured":"Yang, Y., Yan, D., Huanhuan, W., Cheng, J., Zhou, S., Lui, J.C.S.: Diversified temporal subgraph pattern mining. In SIGKDD 1965\u20131974 (2016)","DOI":"10.1145\/2939672.2939848"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-026-00977-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-026-00977-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-026-00977-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T10:18:27Z","timestamp":1778235507000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-026-00977-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,8]]},"references-count":73,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["977"],"URL":"https:\/\/doi.org\/10.1007\/s00778-026-00977-5","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,8]]},"assertion":[{"value":"7 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"25"}}