Synchronous black hole search in directed graphs

DOI10.1016/j.tcs.2011.05.054zbMath1226.68071OpenAlexW1980368207MaRDI QIDQ719316

Adrian Kosowski, Cristina M. Pinotti, Alfredo Navarra

Publication date: 10 October 2011

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

Full work available at URL: https://hal.inria.fr/inria-00614476/file/blackhole.pdf

zbMATH Keywords

graph algorithmsdistributed systemblack hole search problemgraph searching problemmobile agents in graphssynchronous scheduler

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Directed graphs (digraphs), tournaments (05C20) Artificial intelligence for robotics (68T40)

Related Items (3)

Explore and repair graphs with black holes using mobile entities ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Gathering of robots on meeting-points: feasibility and optimal resolution algorithms

Cites Work

• Fast periodic graph exploration with constant memory
• Locating and repairing faults in a network with mobile agents
• Mobile search for a black hole in an anonymous ring
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Time Optimal Algorithms for Black Hole Search in Rings
• Graph Decomposition for Improving Memoryless Periodic Exploration
• Black Hole Search in Directed Graphs
• Approximation bounds for Black Hole Search problems
• Structural Information and Communication Complexity
• Searching for a Black Hole in Synchronous Tree Networks
• Black hole search in common interconnection networks

This page was built for publication: Synchronous black hole search in directed graphs