Approximation bounds for Black Hole Search problems

DOI10.1002/NET.20233MaRDI QIDQ3548722zbMATH OpenOpenAlexFDO

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 algorithmblack hole searchgraph explorationinapproximabilitymobile agent

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 2006651 (Why is no real title available?)
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• 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 arbitrary networks: optimal mobile agents protocols
• Searching for a Black Hole in Synchronous Tree Networks
• Structural Information and Communication Complexity
• TSP with bounded metrics

Cited in

(19)

• Hardness and approximation results for black hole search in arbitrary networks
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Time optimal algorithms for black hole search in rings
• Exploration of Faulty Hamiltonian Graphs
• Black hole search with finite automata scattered in a synchronous torus
• More agents may decrease global work: a case in butterfly decontamination
• Tight bounds for black hole search with scattered agents in synchronous rings
• Improved black hole and multiverse algorithms for discrete sizing optimization of planar structures
• Structural Information and Communication Complexity
• Searching for a Black Hole in Synchronous Tree Networks
• Complexity of searching for a black hole
• Structural Information and Communication Complexity
• On the broadcast problem for mobile agents in dynamic networks
• Searching for black holes in subways
• Synchronous black hole search in directed graphs
• Title not available (Why is no real title available?)
• Explore and repair graphs with black holes using mobile entities
• Exploring an unknown dangerous graph with a constant number of tokens
• Locating and repairing faults in a network with mobile agents

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)