Distributed graph searching with a sense of direction

Piotr Borowiecki; Dariusz Dereniowski; Łukasz Kuszner

doi:10.1007/s00446-014-0236-1

Distributed graph searching with a sense of direction

Abstract

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.

Citations

5

CrossRef
0

Web of Science
6

Scopus

Authors (3)

Cite as

Full text

download paper

downloaded 21 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1007/s00446-014-0236-1
License: open in new tab

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: DISTRIBUTED COMPUTING no. 28, edition 3, pages 155 - 170,
ISSN: 0178-2770
Language:: English
Publication year:: 2015
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
DOI:: Digital Object Identifier (open in new tab) 10.1007/s00446-014-0236-1
Verified by:: Gdańsk University of Technology