Searching for black holes in subways

DOI10.1007/s00224-011-9341-8zbMath1253.68032OpenAlexW2046773087MaRDI QIDQ692936

Peter C. Mason, Matthew Kellett, Paola Flocchini, Nicola 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

zbMATH Keywords

dynamic networksblack hole searchtime-varying graphsmobile agents computing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items (9)

Distributed exploration of dynamic rings ⋮ Shortest, Fastest, and Foremost Broadcast in Dynamic Networks ⋮ Improved periodic data retrieval in asynchronous rings with a faulty host ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Exploration of carrier-based time-varying networks: the power of waiting ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring ⋮ On the expressivity of time-varying graphs

Cites Work

• Unnamed Item
• Mobile search for a black hole in an anonymous ring
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Hardness and approximation results for black hole search in arbitrary networks
• 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
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
• Approximation bounds for Black Hole Search problems
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Exploration of Periodically Varying Graphs
• Measuring Temporal Lags in Delay-Tolerant Networks
• Searching for a Black Hole in Synchronous Tree Networks
• Black hole search in common interconnection networks
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS

This page was built for publication: Searching for black holes in subways