Exploration of \(k\)-edge-deficient temporal graphs. (English) Zbl 07578092
Summary: A temporal graph with lifetime \(L\) is a sequence of \(L\) graphs \(G_1, \ldots ,G_L\), called layers, all of which have the same vertex set \(V\) but can have different edge sets. The underlying graph is the graph with vertex set \(V\) 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 \(k\)-edge-deficient if each layer contains all except at most \(k\) edges of the underlying graph. For a given start vertex \(s\), a temporal exploration is a temporal walk that starts at \(s\), traverses at most one edge in each layer, and visits all vertices of the temporal graph. We show that always-connected, \(k\)-edge-deficient temporal graphs with sufficient lifetime can always be explored in \(O(kn \log n)\) time steps. We also construct always-connected, \(k\)-edge-deficient temporal graphs for which any exploration requires \(\varOmega (n \log k)\) time steps. For always-connected, 1-edge-deficient temporal graphs, we show that \(O(n)\) time steps suffice for temporal exploration.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Akrida, E.C., Mertzios, G.B., Spirakis, P.G.: The temporal explorer who returns to the base. In: P. Heggernes (ed.) 11th International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science, vol. 11485, pp. 13-24. Springer (2019). doi:10.1007/978-3-030-17402-6_2 · Zbl 1477.68191 |
| [2] | Bodlaender, HL; van der Zanden, TC, On exploring always-connected temporal graphs of small pathwidth, Inf. Process. Lett., 142, 68-71 (2019) · Zbl 1469.68072 · doi:10.1016/j.ipl.2018.10.016 |
| [3] | Brodén, B.; Hammar, M.; Nilsson, BJ, Online and offline algorithms for the time-dependent TSP with time zones, Algorithmica, 39, 4, 299-319 (2004) · Zbl 1134.90514 · doi:10.1007/s00453-004-1088-z |
| [4] | Bui-Xuan, B.; Ferreira, A.; Jarry, A., Computing shortest, fastest, and foremost journeys in dynamic networks, Int. J. Found. Comput. Sci., 14, 2, 267-285 (2003) · Zbl 1075.68545 · doi:10.1142/S0129054103001728 |
| [5] | Casteigts, A.; Flocchini, P.; Quattrociocchi, W.; Santoro, N., Time-varying graphs and dynamic networks, Int. J. Parallel Emergent Distrib. Syst., 27, 5, 387-408 (2012) · doi:10.1080/17445760.2012.668546 |
| [6] | Erlebach, T.; Hoffmann, M.; Kammer, F., On temporal graph exploration, J. Comput. Syst. Sci., 119, 1-18 (2021) · Zbl 1477.68222 · doi:10.1016/j.jcss.2021.01.005 |
| [7] | Erlebach, T., Kammer, F., Luo, K., Sajenko, A., Spooner, J.T.: Two Moves per Time Step Make a Difference. In: C. Baier, I. Chatzigiannakis, P. Flocchini, S. Leonardi (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 141:1-141:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). doi:10.4230/LIPIcs.ICALP.2019.141 · Zbl 07561634 |
| [8] | Erlebach, T., Spooner, J.T.: Faster Exploration of Degree-Bounded Temporal Graphs. In: I. Potapov, P. Spirakis, J. Worrell (eds.) 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 117, pp. 36:1-36:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). doi:10.4230/LIPIcs.MFCS.2018.36 · Zbl 1512.68211 |
| [9] | Erlebach, T., Spooner, J.T.: Non-strict Temporal Exploration. In: A.W. Richa, C. Scheideler (eds.) 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2020), Lecture Notes in Computer Science, vol. 12156, pp. 129-145. Springer (2020). doi:10.1007/978-3-030-54921-3_8 · Zbl 07581063 |
| [10] | Erlebach, T., Spooner, J.T.: Exploration of \(k\)-edge-deficient temporal graphs. In: A. Lubiw, M.R. Salavatipour (eds.) 17th International Symposium on Algorithms and Data Structures (WADS 2021), Lecture Notes in Computer Science, vol. 12808, pp. 371-384. Springer (2021). doi:10.1007/978-3-030-83508-8_27 · Zbl 07498690 |
| [11] | Fan, G., Covering graphs by cycles, SIAM J. Discret. Math., 5, 4, 491-496 (1992) · Zbl 0777.05087 · doi:10.1137/0405039 |
| [12] | Frederickson, GN; Johnson, DB, Finding k-th paths and p-centers by generating and searching good data structures, J. Algorithms, 4, 1, 61-80 (1983) · Zbl 0509.68057 · doi:10.1016/0196-6774(83)90035-4 |
| [13] | Gallai, T., Elementare Relationen bezüglich der Glieder und trennenden Punkte von Graphen, Magyar Tud. Akad. Mat. Kutato Int. Kozl, 9, 235-236 (1964) · Zbl 0134.19602 |
| [14] | 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-22:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2020). doi:10.4230/LIPIcs.OPODIS.2019.22 · Zbl 07650872 |
| [15] | Gotoh, T.; Sudo, Y.; Ooshita, F.; Masuzawa, T., Dynamic ring exploration with (H, S) view, Algorithms (2020) · Zbl 1464.68402 · doi:10.3390/a13060141 |
| [16] | Harary, F.; Prins, G., The block-cutpoint-tree of a graph, Publ. Math. Debrecen, 13, 103-107, 19 (1966) · Zbl 0168.44704 |
| [17] | Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of Constantly Connected Dynamic Graphs Based on Cactuses. In: Halldórsson, M.M. (ed.) 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), Lecture Notes in Computer Science, vol. 8576, pp. 250-262. Springer (2014). doi:10.1007/978-3-319-09620-9_20 · Zbl 1416.68192 |
| [18] | 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-23. Springer, Cham (2013). doi:10.1007/978-3-319-03578-9_2 · Zbl 1362.68022 |
| [19] | Kempe, D.; Kleinberg, JM; Kumar, A., Connectivity and inference problems for temporal networks, J. Comput. Syst. Sci., 64, 4, 820-842 (2002) · Zbl 1015.68005 · doi:10.1006/jcss.2002.1829 |
| [20] | 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-343. Springer International Publishing, Cham (2015). doi:10.1007/978-3-319-24024-4_18 · Zbl 1331.68154 |
| [21] | Michail, O.; Spirakis, PG, Traveling salesman problems in temporal graphs, Theor. Comput. Sci., 634, 1-23 (2016) · Zbl 1338.90349 · doi:10.1016/j.tcs.2016.04.006 |
| [22] | 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-596 (1992) · Zbl 0763.05065 · doi:10.1007/BF01758778 |
| [23] | Shannon, C.E.: Presentation of a maze-solving machine. In: Sloane, N.J.A., Wyner A.D. (eds.) Claude Elwood Shannon - Collected Papers, pp. 681-687. IEEE Press (1993) · Zbl 0846.01022 |
| [24] | Zschoche, P.; Fluschnik, T.; Molter, H.; Niedermeier, R., The complexity of finding small separators in temporal graphs, J. Comput. Syst. Sci., 107, 72-92 (2020) · Zbl 1436.68265 · doi:10.1016/j.jcss.2019.07.006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
