Approximation bounds for Black Hole Search problems

DOI10.1002/NET.20233MaRDI QIDQ3548722zbMATHOpenAlexFDO

Authors Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco

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

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

Recommendations

• Hardness and approximation results for black hole search in arbitrary networks
• Structural Information and Communication Complexity
• Complexity of searching for a black hole
• Principles of Distributed Systems
• Searching for a Black Hole in Synchronous Tree Networks

Cites work

• scientific article; zbMATH DE number 2006651 (Why is no real title available?)
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• Black hole search in common interconnection networks
• Complexity of searching for a black hole
• Hardness and approximation results for black hole search in arbitrary networks
• Mobile search for a black hole in an anonymous ring
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Principles of Distributed Systems
• Searching for a Black Hole in Synchronous Tree Networks
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Structural Information and Communication Complexity
• TSP with bounded metrics

Cited in

(17)

• Structural Information and Communication Complexity
• More agents may decrease global work: a case in butterfly decontamination
• 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
• Exploration of Faulty Hamiltonian Graphs
• Structural Information and Communication Complexity
• Improved black hole and multiverse algorithms for discrete sizing optimization of planar structures
• Tight bounds for black hole search with scattered agents in synchronous rings
• Exploring an unknown dangerous graph with a constant number of tokens
• Searching for a Black Hole in Synchronous Tree Networks
• Synchronous black hole search in directed graphs
• Searching for black holes in subways
• Time optimal algorithms for black hole search in rings
• Complexity of searching for a black hole
• Ping pong in dangerous graphs: optimal black hole search with pebbles

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

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