Distributed graph searching with a sense of direction

• DOI: 10.1007/s00446-014-0236-1
• Publication Date: 2014-11-21T14:13:45Z
• Authors: Piotr Borowiecki; Dariusz Dereniowski; Łukasz Kuszner
• Keywords: Neighbourhood (mathematics)

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