Distributed graph searching with a sense of direction - Publikacja - MOST Wiedzy


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


  • 2

    Web of Science

  • 5


Informacje szczegółowe

Publikacja w czasopiśmie
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
DISTRIBUTED COMPUTING nr 28, wydanie 3, strony 155 - 170,
ISSN: 0178-2770
Rok wydania:
Opis bibliograficzny:
Borowiecki P., Dereniowski D., Kuszner Ł.: Distributed graph searching with a sense of direction// DISTRIBUTED COMPUTING. -Vol. 28, iss. 3 (2015), s.155-170
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00446-014-0236-1
Politechnika Gdańska

wyświetlono 14 razy

Publikacje, które mogą cię zainteresować

Meta Tagi