Exploring an unknown dangerous graph with a constant number of tokens

DOI10.1016/j.tcs.2014.07.013zbMath1332.68163OpenAlexW2041241584MaRDI QIDQ896695

Stefan Dobrev, B. Balamohan, Nicola Santoro, Paola Flocchini

Publication date: 10 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.013

zbMATH Keywords

black holedistributed algorithmstokensasynchronous mobile agentsdangerous networksunknown graph exploration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (2)

Distributed exploration of dynamic rings ⋮ Exploration of dynamic tori by multiple agents

Cites Work

• Unnamed Item
• Tight bounds for black hole search with scattered agents in synchronous rings
• Searching for black holes in subways
• Synchronous black hole search in directed graphs
• Locating and repairing faults in a network with mobile agents
• 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
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Map construction of unknown graphs by multiple agents
• Graph exploration by a finite automaton
• TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS
• Black Hole Search with Finite Automata Scattered in a Synchronous Torus
• Black Hole Search in Directed Graphs
• Collective tree exploration
• Approximation bounds for Black Hole Search problems
• Periodic Data Retrieval Problem in Rings Containing a Malicious Host
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Searching for a Black Hole in Synchronous Tree Networks
• Black hole search in common interconnection networks

This page was built for publication: Exploring an unknown dangerous graph with a constant number of tokens