Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
From MaRDI portal
Publication:3540233
DOI10.1007/978-3-540-87779-0_16zbMath1161.68335OpenAlexW1577650777MaRDI QIDQ3540233
David Ilcinkas, Nicola Santoro, Paola Flocchini
Publication date: 20 November 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-87779-0_16
Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Distributed systems (68M14)
Related Items (6)
Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens ⋮ Quiescence of self-stabilizing gossiping among mobile agents in graphs ⋮ Searching for black holes in subways ⋮ Black Hole Search with Finite Automata Scattered in a Synchronous Torus
Cites Work
- Unnamed Item
- Unnamed Item
- Mobile search for a black hole in an anonymous ring
- The power of a pebble: Exploring and mapping directed graphs
- Exploring an unknown dangerous graph using tokens
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Hardness and approximation results for black hole search in arbitrary networks
- Map construction of unknown graphs by multiple agents
- Graph exploration by a finite automaton
- Collective tree exploration
- Black Hole Search in Asynchronous Rings Using Tokens
- Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- Exploring an unknown graph
- Searching for a Black Hole in Synchronous Tree Networks
This page was built for publication: Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
