Digraph Decompositions and Monotonicity in Digraph Searching
From MaRDI portal
Publication:5302067
DOI10.1007/978-3-540-92248-3_30zbMath1202.68285OpenAlexW2154965599MaRDI QIDQ5302067
Sebastian Ordyniak, Stephan Kreutzer
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_30
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57)
Related Items (13)
On the monotonicity of process number ⋮ Entanglement and the complexity of directed graphs ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ The dag-width of directed graphs ⋮ Digraphs of bounded elimination width ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ On complexity of minimum leaf out-branching problem ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ Tree-Width for First Order Formulae ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monotonicity of non-deterministic graph searching
- 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
- Directed tree-width
- Directed path-width and monotonicity in digraph searching
- Directed tree-width examples
- Monotonicity of Non-deterministic Graph Searching
- DAG-width
- Monotonicity in graph searching
- Recontamination does not help to search a graph
- 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
