Wyszukiwarka
Abstrakt
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.
Cytowania
-
5
CrossRef
-
0
Web of Science
-
6
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00446-014-0236-1
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISTRIBUTED COMPUTING
nr 28,
wydanie 3,
strony 155 - 170,
ISSN: 0178-2770 - Język:
- angielski
- Rok wydania:
- 2015
- 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
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00446-014-0236-1
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 128 razy
Publikacje, które mogą cię zainteresować
A Framework for Searching in Graphs in the Presence of Errors
- D. Dereniowski,
- S. Tiegel,
- P. Uznański
- + 1 autorów
Distributed Evacuation in Graphs with Multiple Exits
- P. Borowiecki,
- S. Das,
- D. Dereniowski
- + 1 autorów