Publications Repository - Gdańsk University of Technology

In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w 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 w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has w=1. We assume that with a graph G to be searched, there is associated a partition (V1,...,Vt) of its vertex set such that edges are allowed only within each Vi and between two consecutive Vi'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 Vi leads to a vertex in one of Vi-1, Vi or Vi+1. Starting from any vertex the algorithm uses at most 3max_{i=1,...,t} w(Vi) + 1 searchers, where w(Vi) = SUM_{v∈Vi} w(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 3max_{i=1,...,t} w(Vi) - 1 searchers for some graphs.

Authors

• dr hab. inż. Piotr Borowiecki link open in new tab ,
• prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
• dr inż. Łukasz Kuszner link open in new tab