Graph decomposition for improving memoryless periodic exploration

Adrian Kosowski; Alfredo Navarra

doi:10.1007/978-3-642-03816-7_43

Graph decomposition for improving memoryless periodic exploration

Abstract

W ostatnich latach często badanym problem jest eksploracja anonimowych grafów z lokalnymi etykietami portów przy każdym wierzchołku. Niedawno pokazano [Czyzowicz et al., Proc. SIROCCO'09], że dla każdego grafu istnieje poetykietowanie prowadzące do eksploracji przez automat bezpamięciowy z okresem co najwyżej 13n/3. W niniejszej pracy poprawiamy to ograniczenie do 4n-2, stosując całkowicie nową technikę dekompozycji grafu.

Citations

4

CrossRef
0

Web of Science
7

Scopus

Authors (2)

Cite as

Full text

full text is not available in portal

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

Keywords

Details

Category:: Monographic publication
Type:: rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Title of issue:: Mathematical Foundations of Computer Science 2009 (MFCS 2009) strony 501 - 512
Language:: English
Publication year:: 2009
Bibliographic description:: Kosowski A., Navarra A.: Graph decomposition for improving memoryless periodic exploration // Mathematical Foundations of Computer Science 2009 (MFCS 2009)/ ed. eds. Rastislav Královic, Damian Niwinski Berlin / Heidelberg: Springer, 2009, s.501-512
DOI:: Digital Object Identifier (open in new tab) 10.1007/978-3-642-03816-7_43
Verified by:: Gdańsk University of Technology