Abstract
Exploration is a fundamental task in mobile computing. We study the version where a group of cooperating agents is situated in a graph, and the task is to make sure that every vertex of the graph is visited by some agent. We consider discrete-time evolving graphs with an adaptive adversary: the adversary observes the actions of the agents, and can choose the graph for the next step arbitrarily with the only restriction that it must be connected. We are interested in solving the problem with weakest possible agents. We provide an exploration algorithm where the agents can not interact in any way among themselves or with the vertices (no messages, whiteboards, etc), and even don’t sense each other. They are only aware of the others from the results of a mutual-exclusion mechanism in the vertices. We show that \(2m-n+1\) agents are sufficient, where m is the number of edges. Interestingly, \(m-n+1\) agents are needed even in an offline setting when they are controlled by a central entity.
We don’t know whether the algorithm achieves polynomial exploration time. However, we provide a different algorithm that uses \(O(n^4)\) agents in a slightly stronger model (the agents can observe the number of agents in a vertex, and their actions), but achieves the exploration time \(O(n^9)\).
The research was supported by Slovak grant VEGA 1/0601/20.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
If the domain of \(\lambda \) is of cardinality O(n), then \(O(n\log n)\) bits of local memory will always be sufficient.
References
Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)
Ambühl, C., Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7(2), 17 (2011)
Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16–18 October 1978, pp. 132–142. IEEE Computer Society (1978)
Blum, M., Sakoda, W.J.: On the capability of finite automata in 2 and 3 dimensional space. In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October–1 November 1977, pp. 147–161. IEEE Computer Society (1977)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. IJPEDS 27(5), 387–408 (2012)
Das, S.: Graph explorations with mobile agents. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing. LNCS, vol. 11340, pp. 403–422. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-11072-7_16
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999)
Dobrev, S., Jansson, J., Sadakane, K., Sung, W.-K.: Finding short right-hand-on-the-wall walks in graphs. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 127–139. Springer, Heidelberg (2005). https://doi.org/10.1007/11429647_12
Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 11–22. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_4
Flocchini, P., Mans, B., Santoro, N.: Sense of direction in distributed computing. Theor. Comput. Sci. 291(1), 29–53 (2003)
Flocchini, P., Prencipe, G., Santoro, N. (eds.): Distributed Computing by Mobile Entities, Current Research in Moving and Computing. LNCS, vol. 11340. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-11072-7
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2–3), 331–344 (2005)
Gasieniec, L., Klasing, R., Martin, R.A., Navarra, A., Zhang, X.: Fast periodic graph exploration with constant memory. J. Comput. Syst. Sci. 74(5), 808–822 (2008)
Gąsieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 14–29. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92248-3_2
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), 17–19 December 2019, Neuchâtel, Switzerland. LIPIcs, vol. 153, pp. 22:1–22:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Ilcinkas, D.: Setting port numbers for fast graph exploration. Theor. Comput. Sci. 401(1–3), 236–242 (2008)
Kosowski, A., Navarra, A.: Graph decomposition for memoryless periodic exploration. Algorithmica 63(1–2), 26–38 (2012). https://doi.org/10.1007/s00453-011-9518-1
Di Luna, G., Dobrev, S., Flocchini, P., Santoro, N.: Distributed exploration of dynamic rings. Distrib. Comput. 33(1), 41–67 (2018). https://doi.org/10.1007/s00446-018-0339-1
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281–295 (1999)
Rollik, H.: Automaten in planaren graphen. Acta Inf. 13, 287–298 (1980). https://doi.org/10.1007/BF00288647
Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563–581 (1977)
Steinová, M.: On the power of local orientations. In: Shvartsman, A.A., Felber, P. (eds.) SIROCCO 2008. LNCS, vol. 5058, pp. 156–169. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69355-0_14
Tajibnapis, W.D.: A correctness proof of a topology information maintenance protocol for a distributed computer network. Commun. ACM 20(7), 477–485 (1977)
Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37(3), 165–186 (2003). https://doi.org/10.1007/s00453-003-1030-9
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Dobrev, S., Královič, R., Pardubská, D. (2020). Exploration of Time-Varying Connected Graphs with Silent Agents. In: Richa, A., Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2020. Lecture Notes in Computer Science(), vol 12156. Springer, Cham. https://doi.org/10.1007/978-3-030-54921-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-54921-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54920-6
Online ISBN: 978-3-030-54921-3
eBook Packages: Computer ScienceComputer Science (R0)