Explore and repair graphs with black holes using mobile entities
DOI10.1016/J.TCS.2015.09.002zbMATH Open1330.68222OpenAlexW1835394405MaRDI QIDQ888441FDOQ888441
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
Recommendations
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)
Cites Work
- Emergence of Scaling in Random Networks
- Title not available (Why is that?)
- Random graphs.
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Ping pong in dangerous graphs: optimal black hole search with pebbles
- Approximation bounds for Black Hole Search problems
- Exploring an unknown dangerous graph using tokens
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Time optimal algorithms for black hole search in rings
- Black hole search in directed graphs
- Structural Information and Communication Complexity
- Searching for a Black Hole in Synchronous Tree Networks
- Black hole search in common interconnection networks
- Locating and repairing faults in a network with mobile agents
- Mobile search for a black hole in an anonymous ring
- Uniform random sampling of planar graphs in linear time
- Fast periodic graph exploration with constant memory
- Computing without communicating: ring exploration by asynchronous oblivious robots
- Synchronous black hole search in directed graphs
- Graph decomposition for memoryless periodic exploration
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Memory Efficient Anonymous Graph Exploration
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
Uses Software
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)
