Searching for black holes in subways
DOI10.1007/S00224-011-9341-8zbMATH Open1253.68032OpenAlexW2046773087MaRDI QIDQ692936FDOQ692936
Authors: P. Flocchini, Matthew Kellett, Peter C. Mason, N. Santoro 
Publication date: 6 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9341-8
Recommendations
- Black hole search in common interconnection networks
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Structural Information and Communication Complexity
- Locating and Repairing Faults in a Network with Mobile Agents
- Locating and repairing faults in a network with mobile agents
Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Transportation, logistics and supply chain management (90B06) Network design and communication in computer systems (68M10)
Cites Work
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Approximation bounds for Black Hole Search problems
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Hardness and approximation results for black hole search in arbitrary networks
- Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
- USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
- Exploration of periodically varying graphs
- Searching for a Black Hole in Synchronous Tree Networks
- Black hole search in common interconnection networks
- Complexity of searching for a black hole
- Mobile search for a black hole in an anonymous ring
- Time optimal algorithms for black hole search in rings
- Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
- Locating and Repairing Faults in a Network with Mobile Agents
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- Measuring Temporal Lags in Delay-Tolerant Networks
Cited In (11)
- On the expressivity of time-varying graphs
- Shortest, fastest, and foremost broadcast in dynamic networks
- Black hole search in dynamic cactus graph
- Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring
- Title not available (Why is that?)
- Exploration of Faulty Hamiltonian Graphs
- Distributed exploration of dynamic rings
- Improved periodic data retrieval in asynchronous rings with a faulty host
- Exploring an unknown dangerous graph with a constant number of tokens
- Exploration of dynamic networks: tight bounds on the number of agents
- Exploration of carrier-based time-varying networks: the power of waiting
This page was built for publication: Searching for black holes in subways
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692936)
