{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:49:58Z","timestamp":1762325398311,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T00:00:00Z","timestamp":1661558400000},"content-version":"vor","delay-in-days":26,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S033483\/1","EP\/T01461X\/1"],"award-info":[{"award-number":["EP\/S033483\/1","EP\/T01461X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A temporal graph with lifetime <jats:italic>L<\/jats:italic> is a sequence of <jats:italic>L<\/jats:italic> graphs <jats:inline-formula><jats:alternatives><jats:tex-math>$$G_1, \\ldots ,G_L$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mi>L<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, called layers, all of which have the same vertex set\u00a0<jats:italic>V<\/jats:italic> but can have different edge sets. The underlying graph is the graph with vertex set <jats:italic>V<\/jats:italic> that contains all the edges that appear in at least one layer. The temporal graph is always connected if each layer is a connected graph, and it is <jats:italic>k<\/jats:italic>-edge-deficient if each layer contains all except at most <jats:italic>k<\/jats:italic> edges of the underlying graph. For a given start vertex\u00a0<jats:italic>s<\/jats:italic>, a temporal exploration is a temporal walk that starts at\u00a0<jats:italic>s<\/jats:italic>, traverses at most one edge in each layer, and visits all vertices of the temporal graph. We show that always-connected, <jats:italic>k<\/jats:italic>-edge-deficient temporal graphs with sufficient lifetime can always be explored in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(kn \\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time steps. We also construct always-connected, <jats:italic>k<\/jats:italic>-edge-deficient temporal graphs for which any exploration requires <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (n \\log k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time steps. For always-connected, 1-edge-deficient temporal graphs, we show that <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) time steps suffice for temporal exploration.<\/jats:p>","DOI":"10.1007\/s00236-022-00421-5","type":"journal-article","created":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:07:01Z","timestamp":1661591221000},"page":"387-407","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Exploration of k-edge-deficient temporal graphs"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4470-5868","authenticated-orcid":false,"given":"Thomas","family":"Erlebach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakob T.","family":"Spooner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,27]]},"reference":[{"key":"421_CR1","doi-asserted-by":"publisher","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G.: The temporal explorer who returns to the base. In: P.\u00a0Heggernes (ed.) 11th International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science, vol. 11485, pp. 13\u201324. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-17402-6_2","DOI":"10.1007\/978-3-030-17402-6_2"},{"key":"421_CR2","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2018.10.016","volume":"142","author":"HL Bodlaender","year":"2019","unstructured":"Bodlaender, H.L., van der Zanden, T.C.: On exploring always-connected temporal graphs of small pathwidth. Inf. Process. Lett. 142, 68\u201371 (2019). https:\/\/doi.org\/10.1016\/j.ipl.2018.10.016","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"421_CR3","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s00453-004-1088-z","volume":"39","author":"B Brod\u00e9n","year":"2004","unstructured":"Brod\u00e9n, B., Hammar, M., Nilsson, B.J.: Online and offline algorithms for the time-dependent TSP with time zones. Algorithmica 39(4), 299\u2013319 (2004). https:\/\/doi.org\/10.1007\/s00453-004-1088-z","journal-title":"Algorithmica"},{"issue":"2","key":"421_CR4","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B Bui-Xuan","year":"2003","unstructured":"Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267\u2013285 (2003). https:\/\/doi.org\/10.1142\/S0129054103001728","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"421_CR5","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387\u2013408 (2012). https:\/\/doi.org\/10.1080\/17445760.2012.668546","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"421_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2021.01.005","volume":"119","author":"T Erlebach","year":"2021","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. J. Comput. Syst. Sci. 119, 1\u201318 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2021.01.005","journal-title":"J. Comput. Syst. Sci."},{"key":"421_CR7","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Kammer, F., Luo, K., Sajenko, A., Spooner, J.T.: Two Moves per Time Step Make a Difference. In: C.\u00a0Baier, I.\u00a0Chatzigiannakis, P.\u00a0Flocchini, S.\u00a0Leonardi (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 141:1\u2013141:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.141","DOI":"10.4230\/LIPIcs.ICALP.2019.141"},{"key":"421_CR8","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Spooner, J.T.: Faster Exploration of Degree-Bounded Temporal Graphs. In: I.\u00a0Potapov, P.\u00a0Spirakis, J.\u00a0Worrell (eds.) 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 117, pp. 36:1\u201336:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.36","DOI":"10.4230\/LIPIcs.MFCS.2018.36"},{"key":"421_CR9","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Spooner, J.T.: Non-strict Temporal Exploration. In: A.W. Richa, C.\u00a0Scheideler (eds.) 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2020), Lecture Notes in Computer Science, vol. 12156, pp. 129\u2013145. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-54921-3_8","DOI":"10.1007\/978-3-030-54921-3_8"},{"key":"421_CR10","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Spooner, J.T.: Exploration of $$k$$-edge-deficient temporal graphs. In: A.\u00a0Lubiw, M.R. Salavatipour (eds.) 17th International Symposium on Algorithms and Data Structures (WADS 2021), Lecture Notes in Computer Science, vol. 12808, pp. 371\u2013384. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-83508-8_27","DOI":"10.1007\/978-3-030-83508-8_27"},{"issue":"4","key":"421_CR11","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1137\/0405039","volume":"5","author":"G Fan","year":"1992","unstructured":"Fan, G.: Covering graphs by cycles. SIAM J. Discret. Math. 5(4), 491\u2013496 (1992). https:\/\/doi.org\/10.1137\/0405039","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"421_CR12","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0196-6774(83)90035-4","volume":"4","author":"GN Frederickson","year":"1983","unstructured":"Frederickson, G.N., Johnson, D.B.: Finding k-th paths and p-centers by generating and searching good data structures. J. Algorithms 4(1), 61\u201380 (1983). https:\/\/doi.org\/10.1016\/0196-6774(83)90035-4","journal-title":"J. Algorithms"},{"key":"421_CR13","first-page":"235","volume":"9","author":"T Gallai","year":"1964","unstructured":"Gallai, T.: Elementare Relationen bez\u00fcglich der Glieder und trennenden Punkte von Graphen. Magyar Tud. Akad. Mat. Kutato Int. Kozl 9, 235\u2013236 (1964)","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl"},{"key":"421_CR14","doi-asserted-by":"publisher","unstructured":"Gotoh, T., Flocchini, P., Masuzawa, T., Santoro, N.: Tight Bounds on Distributed Exploration of Temporal Graphs. In: Felber, P., Friedman, R., Gilbert, S., Miller, A. (eds.) 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 153, pp. 22:1\u201322:16. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2019.22","DOI":"10.4230\/LIPIcs.OPODIS.2019.22"},{"key":"421_CR15","doi-asserted-by":"publisher","DOI":"10.3390\/a13060141","author":"T Gotoh","year":"2020","unstructured":"Gotoh, T., Sudo, Y., Ooshita, F., Masuzawa, T.: Dynamic ring exploration with (H, S) view. Algorithms (2020). https:\/\/doi.org\/10.3390\/a13060141","journal-title":"Algorithms"},{"issue":"103\u2013107","key":"421_CR16","first-page":"19","volume":"13","author":"F Harary","year":"1966","unstructured":"Harary, F., Prins, G.: The block-cutpoint-tree of a graph. Publ. Math. Debrecen 13(103\u2013107), 19 (1966)","journal-title":"Publ. Math. Debrecen"},{"key":"421_CR17","doi-asserted-by":"publisher","unstructured":"Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of Constantly Connected Dynamic Graphs Based on Cactuses. In: Halld\u00f3rsson, M.M. (ed.) 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), Lecture Notes in Computer Science, vol. 8576, pp. 250\u2013262. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-09620-9_20","DOI":"10.1007\/978-3-319-09620-9_20"},{"key":"421_CR18","doi-asserted-by":"publisher","unstructured":"Ilcinkas, D., Wade, A.M.: Exploration of the T-interval-connected dynamic graphs: The case of the ring. In: Moscibroda, T., Rescigno, A.A. (eds.) 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013), Lecture Notes in Computer Science, vol. 8179, pp. 13\u201323. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03578-9_2","DOI":"10.1007\/978-3-319-03578-9_2"},{"issue":"4","key":"421_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":"421_CR20","doi-asserted-by":"publisher","unstructured":"Michail, O.: An introduction to temporal graphs: An algorithmic perspective. In: Zaroliagis, C., Pantziou, G., Kontogiannis, S. (eds.) Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday, pp. 308\u2013343. Springer International Publishing, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24024-4_18","DOI":"10.1007\/978-3-319-24024-4_18"},{"key":"421_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","volume":"634","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1\u201323 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.04.006","journal-title":"Theor. Comput. Sci."},{"issue":"5 &6","key":"421_CR22","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse $$k$$-connected spanning subgraph of a $$k$$-connected graph. Algorithmica 7(5 &6), 583\u2013596 (1992). https:\/\/doi.org\/10.1007\/BF01758778","journal-title":"Algorithmica"},{"key":"421_CR23","unstructured":"Shannon, C.E.: Presentation of a maze-solving machine. In: Sloane, N.J.A., Wyner A.D. (eds.) Claude Elwood Shannon \u2013 Collected Papers, pp. 681\u2013687. IEEE Press (1993)"},{"key":"421_CR24","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2019.07.006","volume":"107","author":"P Zschoche","year":"2020","unstructured":"Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding small separators in temporal graphs. J. Comput. Syst. Sci. 107, 72\u201392 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2019.07.006","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00421-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00421-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00421-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:09:36Z","timestamp":1661591376000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00421-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["421"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00421-5","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2022,8]]},"assertion":[{"value":"10 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}