Digraph decompositions and monotonicity in digraph searching

DOI10.1016/j.tcs.2011.05.003zbMath1223.68085OpenAlexW2036443333MaRDI QIDQ638540

Stephan Kreutzer, Sebastian Ordyniak

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.003

zbMATH Keywords

monotonicityentanglementcops and robber gamesgraph searchingDAG-widthKelly-widthdirected path-widthdirected tree-width

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

What’s Next? Future Directions in Parameterized Complexity ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Directed elimination games ⋮ Digraph width measures in parameterized algorithmics ⋮ The treewidth of proofs ⋮ Digraphs of Bounded Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotonicity of non-deterministic graph searching
• Digraph measures: Kelly decompositions, games, and orderings
• An annotated bibliography on guaranteed graph searching
• Sweeping graphs with large clique number
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Fugitive-search games on graphs and related parameters
• On the monotonicity of games generated by symmetric submodular functions.
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Are There Any Good Digraph Width Measures?
• DAG-width
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• On Digraph Width Measures in Parameterized Algorithmics
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• Digraph Decompositions and Monotonicity in Digraph Searching
• Searching for a Visible, Lazy Fugitive
• Digraph Strong Searching: Monotonicity and Complexity
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• Logic for Programming, Artificial Intelligence, and Reasoning

This page was built for publication: Digraph decompositions and monotonicity in digraph searching