Complexity of searching for a black hole

zbMATH Open1095.68078MaRDI QIDQ5480656FDOQ5480656

Authors: Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, Andrzej Pelc 

Publication date: 3 August 2006

Recommendations

• Principles of Distributed Systems
• Approximation bounds for Black Hole Search problems
• Structural Information and Communication Complexity
• Searching for a Black Hole in Synchronous Tree Networks
• Hardness and approximation results for black hole search in arbitrary networks

zbMATH Keywords

graphapproximation algorithmblack holemobile agentNP-hard problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cited In (11)

• Searching for a Black Hole in Synchronous Tree Networks
• Searching for black holes in subways
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Black hole search in dynamic cactus graph
• Collusion Attack from Hubs in The Blockchain Offline Channel Network
• Approximation bounds for Black Hole Search problems
• Exploring an unknown dangerous graph with a constant number of tokens
• Structural Information and Communication Complexity
• Tight bounds for black hole search with scattered agents in synchronous rings
• Locating and Repairing Faults in a Network with Mobile Agents
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens

This page was built for publication: Complexity of searching for a black hole

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