Black Hole Search in Directed Graphs

DOI10.1007/978-3-642-11476-2_15zbMath1274.68271OpenAlexW1495764901MaRDI QIDQ3408170

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

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)

Related Items (6)

Tight bounds for black hole search with scattered agents in synchronous rings ⋮ Explore and repair graphs with black holes using mobile entities ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Synchronous black hole search in directed graphs ⋮ Black Hole Search with Finite Automata Scattered in a Synchronous Torus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The freeze-tag problem: How to wake up a swarm of robots
• Impact of memory size on graph exploration capability
• Tree exploration with advice
• Mobile search for a black hole in an anonymous ring
• The theory of search games and rendezvous.
• On agent-based software engineering
• Graph exploration by a finite automaton
• Collective tree exploration
• Exploring Unknown Undirected Graphs
• Searching for a black hole in arbitrary networks
• STACS 2004
• Structural Information and Communication Complexity
• Principles of Distributed Systems
• Black hole search in common interconnection networks
• Mathematical Foundations of Computer Science 2005
• Structural Information and Communication Complexity
• Principles of Distributed Systems
• Automata, Languages and Programming

This page was built for publication: Black Hole Search in Directed Graphs