Repozytorium publikacji - Politechnika Gdańska

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.

Autorzy

• prof. dr hab. inż. Krzysztof Kosowski link otwiera się w nowej karcie ,
• Alfredo Navarra,
• Cristina Pinotti