{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:55:32Z","timestamp":1763466932433,"version":"3.45.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032091192","type":"print"},{"value":"9783032091208","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T00:00:00Z","timestamp":1763510400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T00:00:00Z","timestamp":1763510400000},"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":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-09120-8_5","type":"book-chapter","created":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:52:10Z","timestamp":1763466730000},"page":"61-75","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Almost Tight Oracles for\u00a0Fastest-Path Queries on\u00a0Temporal Trees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3169-4300","authenticated-orcid":false,"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6976-5579","authenticated-orcid":false,"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8848-7006","authenticated-orcid":false,"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1009-5552","authenticated-orcid":false,"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4543-786X","authenticated-orcid":false,"given":"Alessandro","family":"Straziota","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,19]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","unstructured":"Angrick, S., et al.: How to reduce temporal cliques to find sparse spanners. In: Chan, T.M., Fischer, J., Iacono, J., Herman, G. (eds.) 32nd Annual European Symposium on Algorithms, ESA 2024, 2\u20134 September 2024, Royal Holloway, London, United Kingdom. LIPIcs, vol.\u00a0308, pp. 11:1\u201311:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2024.11","DOI":"10.4230\/LIPICS.ESA.2024.11"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/J.TCS.2003.05.002","volume":"321","author":"MA Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 321(1), 5\u201312 (2004). https:\/\/doi.org\/10.1016\/J.TCS.2003.05.002","journal-title":"Theor. Comput. Sci."},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., Chechik, S., Choudhary, K., Cohen, S., Friedrich, T., Schirneck, M.: Improved distance (sensitivity) oracles with subquadratic space. In: 65th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2024, Chicago, IL, USA, 27\u201330 October 2024, pp. 1550\u20131558. IEEE (2024). https:\/\/doi.org\/10.1109\/FOCS61266.2024.00097","DOI":"10.1109\/FOCS61266.2024.00097"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., D\u2019Angelo, G., Gual\u00e0, L., Leucci, S., Rossi, M.: Sparse temporal spanners with low stretch. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms. ESA 2022, 5\u20139 September 2022, Berlin\/Potsdam, Germany. LIPIcs, vol.\u00a0244, pp. 19:1\u201319:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2022.19","DOI":"10.4230\/LIPICS.ESA.2022.19"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., D\u2019Angelo, G., Gual\u00e0, L., Leucci, S., Rossi, M.: Blackout-tolerant temporal spanners. J. Comput. Syst. Sci. 141, 103495 (2024). https:\/\/doi.org\/10.1016\/J.JCSS.2023.103495","DOI":"10.1016\/J.JCSS.2023.103495"},{"key":"5_CR7","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G., Straziota, A.: Temporal queries for dynamic temporal forests. In: Mestre, J., Wirth, A. (eds.) 35th International Symposium on Algorithms and Computation. ISAAC 2024, 8\u201311 December 2024, Sydney, Australia. LIPIcs, vol.\u00a0322, pp. 11:1\u201311:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.ISAAC.2024.11","DOI":"10.4230\/LIPICS.ISAAC.2024.11"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Brito, L.F.A., Albertini, M.K., Casteigts, A., Traven\u00e7olo, B.A.N.: A dynamic data structure for temporal reachability with unsorted contact insertions. Soc. Netw. Anal. Min. 12 (2021). https:\/\/api.semanticscholar.org\/CorpusID:231847148","DOI":"10.1007\/s13278-021-00851-y"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Brito, L.F.A., Albertini, M.K., Traven\u00e7olo, B.A.N.: A dynamic data structure for representing timed transitive closures on disk. CoRR abs\/2306.13937 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2306.13937","DOI":"10.48550\/ARXIV.2306.13937"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Carnevale, D., Casteigts, A., Corsini, T.: Dismountability in temporal cliques revisited. In: Meeks, K., Scheideler, C. (eds.) 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND 2025, 9\u201311 June 2025, Liverpool, UK. LIPIcs, vol.\u00a0330, pp. 6:1\u20136:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPICS.SAND.2025.6","DOI":"10.4230\/LIPICS.SAND.2025.6"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.JCSS.2021.04.004","volume":"121","author":"A Casteigts","year":"2021","unstructured":"Casteigts, A., Peters, J.G., Schoeters, J.: Temporal cliques admit sparse spanners. J. Comput. Syst. Sci. 121, 1\u201317 (2021). https:\/\/doi.org\/10.1016\/J.JCSS.2021.04.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"5_CR12","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/22M1511916","volume":"53","author":"A Casteigts","year":"2024","unstructured":"Casteigts, A., Raskin, M., Renken, M., Zamaraev, V.: Sharp thresholds in random simple temporal graphs. SIAM J. Comput. 53(2), 346\u2013388 (2024). https:\/\/doi.org\/10.1137\/22M1511916","journal-title":"SIAM J. Comput."},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Chechik, S.: Approximate distance oracles with improved bounds. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing. STOC 2015, Portland, OR, USA, 14\u201317 June 2015, pp. 1\u201310. ACM (2015). https:\/\/doi.org\/10.1145\/2746539.2746562","DOI":"10.1145\/2746539.2746562"},{"key":"5_CR14","doi-asserted-by":"publisher","unstructured":"Dey, D., Gupta, M.: Nearly optimal fault tolerant distance oracle. In: Mohar, B., Shinkar, I., O\u2019Donnell, R. (eds.) Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024, Vancouver, BC, Canada, 24\u201328 June 2024, pp. 944\u2013955. ACM (2024). https:\/\/doi.org\/10.1145\/3618260.3649697","DOI":"10.1145\/3618260.3649697"},{"key":"5_CR15","doi-asserted-by":"publisher","unstructured":"Fernando Afra\u00a0Brito, L., Keese\u00a0Albertini, M., Augusto Nassif\u00a0Traven\u00e7olo, B., Navarro, G.: Dynamic compact data structure for temporal reachability with unsorted contact insertions. Comput. J. 67(10), 2984\u20132994 (2024). https:\/\/doi.org\/10.1093\/comjnl\/bxae063","DOI":"10.1093\/comjnl\/bxae063"},{"key":"5_CR16","doi-asserted-by":"publisher","unstructured":"Goldstein, I., Lewenstein, M., Porat, E.: On the hardness of set disjointness and set intersection with bounded universe. In: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation. ISAAC 2019, 8\u201311 December 2019, Shanghai University of Finance and Economics, Shanghai, China. LIPIcs, vol.\u00a0149, pp. 7:1\u20137:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.ISAAC.2019.7","DOI":"10.4230\/LIPICS.ISAAC.2019.7"},{"issue":"4","key":"5_CR17","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001). https:\/\/doi.org\/10.1145\/502090.502095","journal-title":"J. ACM"},{"issue":"5","key":"5_CR18","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1007\/S00453-019-00641-1","volume":"82","author":"H Kaplan","year":"2020","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Reachability oracles for directed transmission graphs. Algorithmica 82(5), 1259\u20131276 (2020). https:\/\/doi.org\/10.1007\/S00453-019-00641-1","journal-title":"Algorithmica"},{"issue":"4","key":"5_CR19","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/JCSS.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002). https:\/\/doi.org\/10.1006\/JCSS.2002.1829","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-70575-8_8","volume-title":"Automata, Languages and Programming","author":"M Ru\u017ei\u0107","year":"2008","unstructured":"Ru\u017ei\u0107, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 84\u201395. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_8"},{"key":"5_CR21","doi-asserted-by":"publisher","unstructured":"Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721\u2013732 (2014). https:\/\/doi.org\/10.14778\/2732939.2732945","DOI":"10.14778\/2732939.2732945"},{"key":"5_CR22","doi-asserted-by":"publisher","unstructured":"Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: Khanna, S. (ed.) Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2013, New Orleans, Louisiana, USA, 6\u20138 January 2013, pp. 1757\u20131769. SIAM (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.126","DOI":"10.1137\/1.9781611973105.126"}],"container-title":["Lecture Notes in Computer Science","Algorithmics of Wireless Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-09120-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:52:14Z","timestamp":1763466734000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-09120-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,19]]},"ISBN":["9783032091192","9783032091208"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-09120-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,19]]},"assertion":[{"value":"19 November 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ALGOWIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmics of Wireless Networks","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"algosensors2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}