Derandomizing random walks in undirected graphs using locally fair exploration strategies - Publikacja - MOST Wiedzy

Wyszukiwarka

Derandomizing random walks in undirected graphs using locally fair exploration strategies

Abstrakt

W pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia parametrów eksploracji, porównywalnych z błądzeniem losowym. Pokazano, że pierwsza ze zbadanych strategii (OF), która wybiera lokalnie najdawniej użytą krawędź, prowadzi do nieokresowych eksploracji z nierównomiernym obciązeniem krawędzi. Z kolei strategia LUF, która wybiera lokalnie najrzadziej użytą krawędź, osiąga równomierność eksploracji w O(D|E|) krokach, gdzie D oznacza średnicę grafu, a E zbiór jego krawędzi.

Cytowania

  • 4

    CrossRef

  • 0

    Web of Science

  • 5

    Scopus

Cytuj jako

Pełna treść

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

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:
Automata, Languages and Programming(ICALP 2009) strony 411 - 422
Język:
angielski
Rok wydania:
2009
Opis bibliograficzny:
Cooper C., Ilcinkas D., Klasing R., Kosowski A.: Derandomizing random walks in undirected graphs using locally fair exploration strategies// Automata, Languages and Programming(ICALP 2009)/ ed. eds. Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, Wolfgang Thomas. Berlin / Heidelberg: Springer, 2009, s.411-422
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-642-02930-1_34
Weryfikacja:
Politechnika Gdańska

wyświetlono 65 razy

Publikacje, które mogą cię zainteresować

Meta Tagi