Distributed graph searching with a sense of direction - Publication - Bridge of Knowledge


Distributed graph searching with a sense of direction


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.


  • 5


  • 0

    Web of Science

  • 6


Cite as

Full text

full text is not available in portal



artykuł w czasopiśmie wyróżnionym w JCR
Published in:
DISTRIBUTED COMPUTING no. 28, edition 3, pages 155 - 170,
ISSN: 0178-2770
Publication year:
Bibliographic description:
Borowiecki P., Dereniowski D., Kuszner Ł.: Distributed graph searching with a sense of direction// DISTRIBUTED COMPUTING. -Vol. 28, iss. 3 (2015), s.155-170
Digital Object Identifier (open in new tab) 10.1007/s00446-014-0236-1
Verified by:
Gdańsk University of Technology

seen 79 times

Recommended for you

Meta Tags