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

DOI10.1007/978-3-540-87779-0_16zbMATH Open1161.68335OpenAlexW1577650777MaRDI QIDQ3540233FDOQ3540233

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

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

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)

Cites Work

• The power of a pebble: Exploring and mapping directed graphs
• Collective tree exploration
• Title not available (Why is that?)
• Exploring an unknown graph
• Graph exploration by a finite automaton
• Map construction of unknown graphs by multiple agents
• 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
• 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

Cited In (8)

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

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)