Wyszukiwarka
Abstrakt
Praca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano również, że liczba potrzebnych agentów dla grafów skierowanych jest uzależniona od istnienia bądź braku synchroniczności modelu.
Cytowania
-
8
CrossRef
-
0
Web of Science
-
1 3
Scopus
Autorzy (3)
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:
- Principles of distributed systems strony 86 - 98
- Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- Kosowski K., Navarra A., Pinotti C.: Synchronization helps robots to detect black holes in directed graphs// Principles of distributed systems/ ed. eds. Tarek F. Abdelzaher, Michel Raynal, Nicola Santoro. Berlin Heidelberg: Springer, 2009, s.86-98
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-642-10877-8_9
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 88 razy
Publikacje, które mogą cię zainteresować
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 autorów
2009