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.
Authors
- prof. dr hab. inż. Krzysztof Kosowski link open in new tab ,
- Alfredo Navarra,
- Cristina Pinotti
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1007/978-3-642-10877-8_9
- Category
- Publikacja monograficzna
- Type
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Language
- angielski
- Publication year
- 2009
