Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens

DOI10.1007/978-3-540-87779-0_16MaRDI QIDQ3540233zbMATH OpenOpenAlexFDO

Authors David Ilcinkas, P. Flocchini, N. Santoro

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

zbMATH Keywords

distributed computinggraph explorationmobile agentsautonomous robotsdangerous graphs

Mathematics Subject Classification ID

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)

Recommendations

• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Principles of Distributed Systems
• Black Hole Search in Asynchronous Rings Using Tokens
• Exploring an unknown dangerous graph using tokens
• Black hole search with finite automata scattered in a synchronous torus

Cites work

• scientific article; zbMATH DE number 1559557 (Why is no real title available?)
• Black Hole Search in Asynchronous Rings Using Tokens
• Collective tree exploration
• Complexity of searching for a black hole
• Exploring an unknown dangerous graph using tokens
• Exploring an unknown graph
• Graph exploration by a finite automaton
• Hardness and approximation results for black hole search in arbitrary networks
• Map construction of unknown graphs by multiple agents
• Mobile search for a black hole in an anonymous ring
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
• Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
• Searching for a Black Hole in Synchronous Tree Networks
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• The power of a pebble: Exploring and mapping directed graphs

Cited in

(8)

• Black hole search with finite automata scattered in a synchronous torus
• Exploring an unknown dangerous graph using tokens
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
• Black hole search despite Byzantine agents
• Searching for black holes in subways
• Quiescence of self-stabilizing gossiping among mobile agents in graphs
• Ping pong in dangerous graphs: optimal black hole search with pebbles

This page was built for publication: Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens

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