id: 05674862
dt: a
an: 05674862
au: Czyzowicz, Jurek; Dobrev, Stefan; Královič, Rastislav; Miklík,
    Stanislav; Pardubská, Dana
ti: Black hole search in directed graphs.
so: Kutten, Shay (ed.) et al., Structural information and communication
    complexity. 16th international colloquium, SIROCCO 2009, Piran,
    Slovenia, May 25‒27, 2009. Revised selected papers. Berlin: Springer
    (ISBN 978-3-642-11475-5/pbk). Lecture Notes in Computer Science 5869,
    182-194 (2010).
py: 2010
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-11476-2_15
ab: Summary: We consider the problem of cooperative network exploration by
    agents under the assumption that there is a harmful host present in the
    network that destroys the incoming agents without outside trace ‒ the
    so-called black hole search problem. Many variants of this problem have
    been studied, with various assumptions about the timing, agents’
    knowledge about the topology, means of inter-agent communication,
    amount of writable memory in vertices, and other parameters. However,
    all this research considered undirected graphs only, and relied to some
    extent on the ability of an agent to mark an edge as safe immediately
    after having traversed it. In this paper we study directed graphs where
    this technique does not apply, and show that the consequence is an
    exponential gap: While in undirected graphs $Δ+ 1$ agents are always
    sufficient, in the directed case at least $2^Δ$ agents are needed in
    the worst case, where $Δ$ is in-degree of the black hole. This lower
    bound holds also in the case of synchronous agents. Furthermore, we ask
    the question What structural information is sufficient to close this
    gap? and show that in planar graphs with a planar embedding known to
    the agents, $2Δ+ 1$ agents are sufficient, and $2Δ$ agents are
    necessary.
rv: