Black hole search in directed graphs

DOI10.1007/978-3-642-11476-2_15MaRDI QIDQ3408170zbMATH OpenOpenAlexFDO

Authors Jurek Czyzowicz, Stefan Dobrev, Rastislav Královič, Stanislav Miklík, Dana Pardubská

Publication date 24 February 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11476-2_15

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Synchronous black hole search in directed graphs
• Principles of Distributed Systems
• Hardness and approximation results for black hole search in arbitrary networks
• Searching for a Black Hole in Synchronous Tree Networks
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols

Cites work

• Automata, Languages and Programming
• Black hole search in common interconnection networks
• Collective tree exploration
• Exploring Unknown Undirected Graphs
• Graph exploration by a finite automaton
• scientific article; zbMATH DE number 3722098 (Why is no real title available?)
• scientific article; zbMATH DE number 3554185 (Why is no real title available?)
• scientific article; zbMATH DE number 2013391 (Why is no real title available?)
• scientific article; zbMATH DE number 1775412 (Why is no real title available?)
• Impact of memory size on graph exploration capability
• Mathematical Foundations of Computer Science 2005
• Mobile search for a black hole in an anonymous ring
• On agent-based software engineering
• Principles of Distributed Systems
• Principles of Distributed Systems
• Searching for a black hole in arbitrary networks, optimal mobile agent protocols
• STACS 2004
• Structural Information and Communication Complexity
• Structural Information and Communication Complexity
• The theory of search games and rendezvous.
• Tree exploration with advice
• Tree exploration with logarithmic memory

Cited in

(8)

• Hardness and approximation results for black hole search in arbitrary networks
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Black hole search with finite automata scattered in a synchronous torus
• Tight bounds for black hole search with scattered agents in synchronous rings
• Principles of Distributed Systems
• Synchronous black hole search in directed graphs
• Explore and repair graphs with black holes using mobile entities
• Exploring an unknown dangerous graph with a constant number of tokens

This page was built for publication: Black hole search in directed graphs

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