Approximation bounds for Black Hole Search problems
From MaRDI portal
Publication:3548722
DOI10.1002/NET.20233zbMATH Open1157.68073OpenAlexW4214492366MaRDI QIDQ3548722FDOQ3548722
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
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)
Cites Work
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Title not available (Why is that?)
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Hardness and approximation results for black hole search in arbitrary networks
- Searching for a Black Hole in Synchronous Tree Networks
- Black hole search in common interconnection networks
- Complexity of searching for a black hole
- Mobile search for a black hole in an anonymous ring
- TSP with bounded metrics
- Title not available (Why is that?)
- Principles of Distributed Systems
- Structural Information and Communication Complexity
Cited In (17)
- Searching for a Black Hole in Synchronous Tree Networks
- Searching for black holes in subways
- Ping pong in dangerous graphs: optimal black hole search with pebbles
- Locating and repairing faults in a network with mobile agents
- Complexity of searching for a black hole
- Synchronous black hole search in directed graphs
- Hardness and approximation results for black hole search in arbitrary networks
- Explore and repair graphs with black holes using mobile entities
- Exploration of Faulty Hamiltonian Graphs
- Structural Information and Communication Complexity
- Exploring an unknown dangerous graph with a constant number of tokens
- Time optimal algorithms for black hole search in rings
- Structural Information and Communication Complexity
- More agents may decrease global work: a case in butterfly decontamination
- Tight bounds for black hole search with scattered agents in synchronous rings
- Black hole search with finite automata scattered in a synchronous torus
- Improved black hole and multiverse algorithms for discrete sizing optimization of planar structures
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)
