Searching for a Black Hole in Synchronous Tree Networks

DOI10.1017/S0963548306008133zbMath1130.68029OpenAlexW2130524435MaRDI QIDQ5437234

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

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

Related Items (17)

Fault-tolerant sequential scan ⋮ TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ Hardness and approximation results for black hole search in arbitrary networks ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ Tight bounds for black hole search with scattered agents in synchronous rings ⋮ Explore and repair graphs with black holes using mobile entities ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens ⋮ Approximation bounds for Black Hole Search problems ⋮ Locating and repairing faults in a network with mobile agents ⋮ Searching for black holes in subways ⋮ Synchronous black hole search in directed graphs ⋮ USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS ⋮ Black Hole Search with Finite Automata Scattered in a Synchronous Torus

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