Searching for a Black Hole in Synchronous Tree Networks

DOI10.1017/S0963548306008133MaRDI QIDQ5437234zbMATHOpenAlexFDO

Authors Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, Andrzej Pelc

Publication date 18 January 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548306008133

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Fault detection; testing in circuits and networks (94C12)

Recommendations

• Principles of Distributed Systems
• Complexity of searching for a black hole
• Structural Information and Communication Complexity
• Approximation bounds for Black Hole Search problems
• Hardness and approximation results for black hole search in arbitrary networks

Cited in

(25)

• Black hole search in directed graphs
• Structural Information and Communication Complexity
• Locating and repairing faults in a network with mobile agents
• Explore and repair graphs with black holes using mobile entities
• Hardness and approximation results for black hole search in arbitrary networks
• Black hole search with finite automata scattered in a synchronous torus
• Time optimal algorithms for black hole search in rings
• Exploration of Faulty Hamiltonian Graphs
• Principles of Distributed Systems
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Black hole search in dynamic cactus graph
• Approximation bounds for Black Hole Search problems
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Tight bounds for black hole search with scattered agents in synchronous rings
• Exploring an unknown dangerous graph with a constant number of tokens
• Identifying hostile nodes in networks using mobile agents
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
• Black hole search despite Byzantine agents
• Synchronous black hole search in directed graphs
• Searching for black holes in subways
• Time optimal algorithms for black hole search in rings
• Efficient grid exploration with a stationary token
• Complexity of searching for a black hole
• Fault-tolerant sequential scan
• Ping pong in dangerous graphs: optimal black hole search with pebbles

This page was built for publication: Searching for a Black Hole in Synchronous Tree Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5437234)