Approximation bounds for Black Hole Search problems

DOI10.1002/net.20233zbMath1157.68073OpenAlexW4214492366MaRDI QIDQ3548722

Tomasz Radzik, Fabiano Sarracco, Ralf Klasing, Euripides Markou

Publication date: 17 December 2008

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20233

zbMATH Keywords

approximation algorithminapproximabilitymobile agentgraph explorationblack hole search

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (11)

TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ More agents may decrease global work: a case in butterfly decontamination ⋮ 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 ⋮ Locating and repairing faults in a network with mobile agents ⋮ Searching for black holes in subways ⋮ Synchronous black hole search in directed graphs ⋮ Black Hole Search with Finite Automata Scattered in a Synchronous Torus

Cites Work

• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Mobile search for a black hole in an anonymous ring
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Hardness and approximation results for black hole search in arbitrary networks
• TSP with bounded metrics
• Searching for a Black Hole in Synchronous Tree Networks
• Black hole search in common interconnection networks
• Structural Information and Communication Complexity
• Principles of Distributed Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation bounds for Black Hole Search problems