Digraph decompositions and monotonicity in digraph searching
From MaRDI portal
Publication:638540
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
monotonicityentanglementcops and robber gamesgraph searchingDAG-widthKelly-widthdirected path-widthdirected tree-width
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
