Black hole search and exploration in unoriented tori with synchronous scattered finite automata
Data
2012Soggetto
Abstract
We consider the problem of locating a black hole in a synchronous, anonymous, and unoriented torus network using mobile agents. A black hole is a harmful network node that destroys any agent visiting it without leaving any trace. The objective is to locate the black hole using as few agents as possible. We present here an almost optimal deterministic algorithm for synchronous (partially) unoriented tori using five scattered agents with constant memory and three identical tokens. We also study the exploration problem of a safe (i.e., without black holes) unoriented torus. While it has been previously shown that there is no universal algorithm for one agent with constant memory and any constant number of tokens which can explore all cubic planar graphs, we give here the first algorithm which enables a finite automaton with two tokens to explore (without termination detection) any totally unoriented torus and we prove optimality on the number of tokens. © 2012 Springer-Verlag.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Detecting and Locating Gastrointestinal Anomalies Using Deep Learning and Iterative Cluster Unification
Iakovidis D.K., Georgakopoulos S.V., Vasilakakis M., Koulaouzidis A., Plagianakos V.P. (2018)This paper proposes a novel methodology for automatic detection and localization of gastrointestinal (GI) anomalies in endoscopic video frame sequences. Training is performed with weakly annotated images, using only ... -
Joint QoS multicast power / admission control and base station assignment: A geometric programming approach
Karipidis, E.; Sidiropoulos, N. D.; Tassiulas, L. (2008)The joint power control and base station (BS) assignment problem is considered under Quality-of-Service (QoS) constraints. If a feasible solution exists, the problem can be efficiently solved using existing distributed ... -
Biological-inspired algorithms for dynamic search in web graphs
Kouzas, G.; Anagnostopoulos, I. (2011)We propose a biological-inspired algorithmic procedure for improving the precision level in respect to a web user's query. This algorithm is capable of tracing relevant information in web graphs, imitating the mission of ...