Graph Decomposition for Memoryless Periodic Exploration

Adrian Kosowski; Alfredo Navarra

doi:10.1007/s00453-011-9518-1

Graph Decomposition for Memoryless Periodic Exploration

Abstrakt

We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels within the range 1 to deg (v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex v via the edge labeled i, the robot proceeds with its exploration, leaving via the edge having label [i mod deg (v)]+1 at v.A lot of attention has been given to the problem of labeling the graph so as to achieve a periodic exploration having the minimum possible length π. It has recently been proved (Czyzowicz et al., Proc. SIROCCO'09, 2009) that π ≤ 13/3 n holds for all graphs of n vertices. Herein, we provide a new labeling scheme which leads to shorter exploration cycles, improving the general bound to π≤4n−2. This main result is shown to be tight with respect to the class of labellings admitting certain connectivity properties. The labeling scheme is based on a new graph decomposition which may be of independent interest.

Cytowania

1 5

CrossRef
0

Web of Science
1 6

Scopus

Autorzy (2)

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym 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:: ALGORITHMICA nr 63, strony 26 - 38,
ISSN: 0178-4617
Język:: angielski
Rok wydania:: 2012
Opis bibliograficzny:: Kosowski A., Navarra A.: Graph Decomposition for Memoryless Periodic Exploration // ALGORITHMICA. -Vol. 63, nr. Iss. 1-2 (2012), s.26-38
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00453-011-9518-1
Weryfikacja:: Politechnika Gdańska