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

Abstrakt

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.

Cytowania

4

CrossRef
0

Web of Science
7

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 monograficzna
Typ:: rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Tytuł wydania:: Mathematical Foundations of Computer Science 2009 (MFCS 2009) strony 501 - 512
Język:: angielski
Rok wydania:: 2009
Opis bibliograficzny:: 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:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-642-03816-7_43
Weryfikacja:: Politechnika Gdańska