Abstract
A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with n nodes, we show that it is \(\mathbf {NP}\)-hard to approximate TEXP with ratio \(O(n^{1-\varepsilon })\) for any \(\varepsilon >0\). We also provide an explicit construction of temporal graphs that require \(\Theta (n^2)\) steps to be explored. We then consider TEXP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in \(O(n^{1.5}k^2\log n)\) steps if the underlying graph has treewidth k and in \(O(n\log ^3 n)\) steps if the underlying graph is a \(2 \times n\) grid. We also show that sparse temporal graphs with regularly present edges can always be explored in O(n) steps.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Ajtai, M., Komlós, J., Szemerédi, E.: Largest random component of a k-cube. Combinatorica 2(1), 1–7 (1982)
Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger’s theorem. Networks 28(3), 125–134 (1996)
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)
Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. In: Proc. 25th Conference on IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2011), pp. 209–218. IEEE (2011)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. IJPEDS 27(5), 387–408 (2012)
Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. CoRR abs/1504.07976 (2015). arXiv: 1504.07976
Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 534–543. Springer, Heidelberg (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco (1979)
Karlin, A.R., Nelson, G., Tamaki, H.: On the fault tolerance of the butterfly. In: Proc. 26th Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 125–133. ACM (1994)
Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)
Kesten, H.: The critical probability of bond percolation on the square lattice equals \({1\over 2}\). Comm. Math. Phys. 74(1), 41–59 (1980)
Kloks, T. (ed.): Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994)
Liu, C., Wu, J.: Scalable routing in cyclic mobile networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1325–1338 (2009)
Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013)
Michail, O.: An introduction to temporal graphs: An algorithmic perspective. CoRR abs/1503.00278 (2015). arXiv: 1503.00278
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 553–564. Springer, Heidelberg (2014)
Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical Report 396, Department of Mathematics, Techni-sche Universität Berlin (1994)
Scheideler, C.: Models and techniques for communication in dynamic networks. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 27–49. Springer, Heidelberg (2002)
Shannon, C.: Presentation of a maze-solving machine. In: Proc. 8th Conference of the Josiah Macy Jr. Found (Cybernetics), pp. 173–180 (1951)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Erlebach, T., Hoffmann, M., Kammer, F. (2015). On Temporal Graph Exploration. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_36
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)