Explore and repair graphs with black holes using mobile entities

DOI10.1016/j.tcs.2015.09.002zbMath1330.68222OpenAlexW1835394405MaRDI QIDQ888441

Mattia D'Emidio, Alfredo Navarra, Daniele Frigioni

Publication date: 30 October 2015

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

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

zbMATH Keywords

experimentstime complexityblack-holesexploration algorithmsmobile entities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (4)

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane ⋮ Gathering of robots on meeting-points: feasibility and optimal resolution algorithms ⋮ Gathering of robots in a ring with mobile faults ⋮ Bamboo garden trimming problem: priority schedulings

Uses Software

• OMNet++

Cites Work

• Unnamed Item
• Unnamed Item
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Synchronous black hole search in directed graphs
• 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
• Exploring an unknown dangerous graph using tokens
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Graph decomposition for memoryless periodic exploration
• TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS
• Uniform random sampling of planar graphs in linear time
• Emergence of Scaling in Random Networks
• Distance-d Independent Set Problems for Bipartite and Chordal Graphs
• Black Hole Search in Directed Graphs
• Approximation bounds for Black Hole Search problems
• Memory Efficient Anonymous Graph Exploration
• 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: Explore and repair graphs with black holes using mobile entities