Hardness and approximation results for black hole search in arbitrary networks

DOI10.1016/j.tcs.2007.04.024zbMath1125.68139OpenAlexW2099846147MaRDI QIDQ2382674

Fabiano Sarracco, Tomasz Radzik, Ralf Klasing, Euripides Markou

Publication date: 2 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00070349/file/RR-5659.pdf

zbMATH Keywords

NP-hardnessApproximation algorithmmobile agentgraph explorationblack hole search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

Tight bounds for black hole search with scattered agents in synchronous rings ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Locating and Repairing Faults in a Network with Mobile Agents ⋮ 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 ⋮ Gathering of robots in a ring with mobile faults ⋮ Approximation bounds for Black Hole Search problems ⋮ Locating and repairing faults in a network with mobile agents ⋮ Searching for black holes in subways ⋮ Black Hole Search with Finite Automata Scattered in a Synchronous Torus

Cites Work

• Unnamed Item
• Unnamed Item
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Spanning Trees with Many Leaves
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Searching for a Black Hole in Synchronous Tree Networks
• Principles of Distributed Systems
• Black hole search in common interconnection networks
• Structural Information and Communication Complexity

This page was built for publication: Hardness and approximation results for black hole search in arbitrary networks