Ett svart hål är en skadlig värd som förstör inkommande agenter utan att lämna några synliga spår av en sådan förstörelse. Det svarta hålets sökproblem är att entydigt bestämma var det svarta hålet finns. Ett team av agenter, som förses med en nätverkskarta och utför samma protokoll, löser problemet om minst en agent överlever och, inom ändlig tid, vet platsen för det svarta hålet. Det är känt att ett team måste ha minst två agenter. Intressant nog kan två agenter med en karta över nätverket lokalisera det svarta hålet med O(n) flyttar i många mycket regelbundna nätverk; men protokollen som används gäller endast för en smal klass av nätverk. Å andra sidan måste alla universella lösning protokoll använda  och (n log n) flyttar i värsta fall, oavsett storleken på laget. Ett universellt lösningsprotokoll har nyligen presenterats som använder ett team av bara två agenter med en karta över nätverket, och lokaliserar ett svart hål i högst O (n log n) flyttar. Således har detta protokoll både optimal storlek och värsta-fall-optimal kostnad. Vi visar att detta resultat, långt ifrån att avsluta forskningsuppdraget, kan förbättras avsevärt. I detta dokument presenterar vi ett universellt protokoll som gör det möjligt för ett team av två agenter med en nätverkskarta att lokalisera det svarta hålet med hjälp av högst O(n + d log d) flyttar, där d är diametern på nätverket. Detta innebär att denna algoritm, utan att förlora sin universalitet och utan att bryta mot det värsta fallet, tillåter två agenter att lokalisera ett svart hål med kostnader i en mycket stor klass av (eventuellt ostrukturerade) nätverk.
Förbättrade gränser för antalet rörelser har senare erhållits i det fall agenterna har en fullständig karta över nätverket (men inte platsen för Bh) REF.
Improved bounds for optimal black hole search in a network with a map
{'venue': 'In Proc. of 10th International Colloquium on Structural Information and Communication Complexity', 'journal': None, 'mag_field_of_study': ['Computer Science']}