Distributed graph searching with a sense of direction
Piotr Borowiecki, Dariusz Dereniowski, Łukasz Kuszner · Distributed Computing · 2014
In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function $${\omega }$$ provides for each vertex $$v$$ the minimum number of searchers required to guard $$v$$ , i.e., the fugitive may not pass through $$v$$ without being detected only if at least $${\omega }(v)$$ searchers are present at $$v$$ . This problem is a generalization of the classical edge searching problem, in which one has $${\omega }\equiv 1$$ . We assume that with a graph $$G$$ to be searched, there is associated a partition $$(V_1,\ldots ,V_t)$$ of its vertex set such that edges are allowed only within each $$V_i$$ and between two consecutive $$V_i$$ ’s. We provide an algorithm for distributed monotone connected edge searching of such graphs, where the searchers are initially placed on an arbitrary vertex of $$G$$ and have no a priori knowledge on $$G$$ , but they have a sense of direction that lets them recognize whether an edge incident to already explored vertex in $$V_i$$ leads to a vertex in one of $$V_{i-1}, V_i$$ or $$V_{i+1}$$ . Starting from any vertex the algorithm uses at most $$3\cdot \max _{i=1,\ldots ,t}{\omega }(V_i)+1$$ searchers, where $${\omega }(V_i) = \sum _{v\in V_i}{\omega }(v)$$ . We also prove that this algorithm is best possible up to a small additive constant, that is, each distributed searching algorithm in worst case must use $$3\cdot \max _{i=1,\ldots ,t}{\omega }(V_i)-1$$ searchers for some graphs.