TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS

DOI10.1142/S1793830911001346zbMath1255.68285OpenAlexW2022437016MaRDI QIDQ2905278

B. Balamohan, Ali Miri, Paola Flocchini, Nicola Santoro

Publication date: 27 August 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830911001346

zbMATH Keywords

ringblack holemobile agentsgraph explorationdangerous networks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed algorithms (68W15)

Related Items (5)

Tight bounds for black hole search with scattered agents in synchronous rings ⋮ 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 ⋮ Gathering of robots on meeting-points: feasibility and optimal resolution algorithms

Cites Work

• Mobile search for a black hole in an anonymous ring
• The power of a pebble: Exploring and mapping directed graphs
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Graph exploration by a finite automaton
• Approximation bounds for Black Hole Search problems
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Exploring an unknown graph
• Searching for a Black Hole in Synchronous Tree Networks
• Black hole search in common interconnection networks

This page was built for publication: TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS