Explore and repair graphs with black holes using mobile entities

DOI10.1016/J.TCS.2015.09.002MaRDI QIDQ888441zbMATH OpenOpenAlexFDO

Authors Mattia D'Emidio, Daniele Frigioni, Alfredo Navarra

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

time complexityexperimentsblack-holesexploration algorithmsmobile entities

Mathematics Subject Classification ID

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

Recommendations

• Synchronous black hole search in directed graphs
• Hardness and approximation results for black hole search in arbitrary networks
• Structural Information and Communication Complexity
• Exploring an unknown dangerous graph using tokens
• Time optimal algorithms for black hole search in rings

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximation bounds for Black Hole Search problems
• Black hole search in common interconnection networks
• Black hole search in directed graphs
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Emergence of Scaling in Random Networks
• Exploring an unknown dangerous graph using tokens
• Fast periodic graph exploration with constant memory
• Graph decomposition for memoryless periodic exploration
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Locating and repairing faults in a network with mobile agents
• Memory Efficient Anonymous Graph Exploration
• Mobile search for a black hole in an anonymous ring
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Random graphs.
• Searching for a Black Hole in Synchronous Tree Networks
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Structural Information and Communication Complexity
• Synchronous black hole search in directed graphs
• Time optimal algorithms for black hole search in rings
• Uniform random sampling of planar graphs in linear time

Cited in

(5)

• Bamboo garden trimming problem: priority schedulings
• Gathering of robots in a ring with mobile faults
• 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
• Synchronous black hole search in directed graphs

Describes a project that uses

Uses Software

• OMNet++

This page was built for publication: Explore and repair graphs with black holes using mobile entities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888441)