Ping pong in dangerous graphs: optimal black hole search with pebbles

DOI10.1007/S00453-011-9496-3MaRDI QIDQ2429323zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

distributed computingblack holegraph explorationmobile agents

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 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

Cites work

• Approximation bounds for Black Hole Search problems
• Black Hole Search in Asynchronous Rings Using Tokens
• Black hole search in directed graphs
• Collective tree exploration
• Complexity of searching for a black hole
• Exploring Unknown Environments
• 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
• Periodic data retrieval problem in rings containing a malicious host (extended abstract)
• 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

(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)