Ping pong in dangerous graphs: optimal black hole search with pebbles
DOI10.1007/S00453-011-9496-3zbMATH Open1247.68028OpenAlexW1967767406MaRDI QIDQ2429323FDOQ2429323
Authors: P. Flocchini, David Ilcinkas, N. Santoro 
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9496-3
Recommendations
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Structural Information and Communication Complexity
- Time optimal algorithms for black hole search in rings
- Mobile search for a black hole in an anonymous ring
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)
Cites Work
- The power of a pebble: Exploring and mapping directed graphs
- Collective tree exploration
- Exploring an unknown graph
- Graph exploration by a finite automaton
- Map construction of unknown graphs by multiple agents
- Approximation bounds for Black Hole Search problems
- Exploring Unknown Environments
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Hardness and approximation results for black hole search in arbitrary networks
- Black hole search in directed graphs
- Black Hole Search in Asynchronous Rings Using Tokens
- Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
- Searching for a Black Hole in Synchronous Tree Networks
- Complexity of searching for a black hole
- Mobile search for a black hole in an anonymous ring
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- Periodic data retrieval problem in rings containing a malicious host (extended abstract)
Cited In (7)
- Fast rendezvous on a cycle by agents with different speeds
- Explore and repair graphs with black holes using mobile entities
- Improved periodic data retrieval in asynchronous rings with a faulty host
- Exploring an unknown dangerous graph with a constant number of tokens
- More agents may decrease global work: a case in butterfly decontamination
- Tight bounds for black hole search with scattered agents in synchronous rings
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
This page was built for publication: Ping pong in dangerous graphs: optimal black hole search with pebbles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429323)
