Complexity of searching for a black hole

MaRDI QIDQ5480656zbMATH OpenFDO

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

Publication date 3 August 2006

zbMATH Keywords

graphapproximation algorithmblack holemobile agentNP-hard problem

Mathematics Subject Classification ID

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

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

Cited in

(12)

• Structural Information and Communication Complexity
• Collusion attack from hubs in the blockchain offline channel network
• Locating and Repairing Faults in a Network with Mobile Agents
• Black hole search in dynamic cactus graph
• Approximation bounds for Black Hole Search problems
• Tight bounds for black hole search with scattered agents in synchronous rings
• Exploring an unknown dangerous graph with a constant number of tokens
• Identifying hostile nodes in networks using mobile agents
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
• 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

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)