Digraphs of Bounded Width
From MaRDI portal
Publication:3120441
DOI10.1007/978-3-319-71840-8_9zbMath1407.05113OpenAlexW2809076337MaRDI QIDQ3120441
O-joung Kwon, Stephan Kreutzer
Publication date: 4 March 2019
Published in: Springer Monographs in Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-71840-8_9
Related Items
Spined categories: generalizing tree-width beyond graphs, Directed Path-Decompositions, Synchronizing series-parallel deterministic finite automata with loops and related problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An algorithmic metatheorem for directed treewidth
- Computing directed pathwidth in \(O(1.89^n)\) time
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- The dag-width of directed graphs
- Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
- Edge-disjoint paths in digraphs with bounded independence number
- Approximation algorithms for digraph width parameters
- Disjoint paths in tournaments
- Forbidden directed minors and Kelly-width
- Digraph decompositions and monotonicity in digraph searching
- Directed width parameters and circumference of digraphs
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Are there any good digraph width measures?
- Directed NLC-width
- Digraph measures: Kelly decompositions, games, and orderings
- An annotated bibliography on guaranteed graph searching
- Recognizing digraphs of Kelly-width 2
- The rank-width of the square grid
- Colouring graphs with bounded generalized colouring number
- Graph minors. V. Excluding a planar graph
- Isotropic systems
- Graphic presentations of isotropic systems
- Reducing prime graphs and recognizing circle graphs
- The directed subgraph homeomorphism problem
- Complement reducible graphs
- Graph minors. X: Obstructions to tree-decomposition
- Graph searching and a min-max theorem for tree-width
- \(k\)-NLC graphs and polynomial algorithms
- Packing directed circuits
- Characterising bounded expansion by neighbourhood complexity
- Orderings on graphs and game coloring number
- Directed tree-width
- Edge dominating set and colorings on graphs with fixed clique-width
- Entanglement and the complexity of directed graphs
- A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
- Constant-factor approximation of the domination number in sparse graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- A trichotomy for regular simple path queries on graphs
- Handle-rewriting hypergraph grammars
- The rank-width of edge-coloured graphs
- Rank-width: algorithmic and structural results
- Grad and classes with bounded expansion. I: Decompositions
- On nowhere dense graphs
- Digraphs of bounded elimination width
- Digraph width measures in parameterized algorithmics
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- Directed path-width and monotonicity in digraph searching
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Rank-width and vertex-minors
- Directed tree-width examples
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- DAG-Width and Circumference of Digraphs
- On the structure of graphs with path-width at most two
- The Directed Grid Theorem
- Intractability of Clique-Width Parameterizations
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- DAG-width
- Clique-Width and Parity Games
- Rank-Width and Well-Quasi-Ordering
- On Digraph Width Measures in Parameterized Algorithmics
- Complexity of Finding Embeddings in a k-Tree
- Decomposition of Directed Graphs
- Monotonicity in graph searching
- Deciding First-Order Properties of Nowhere Dense Graphs
- Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
- Approximating rank-width and clique-width quickly
- Half-integral linkages in highly connected directed graphs
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- DAG-Width and Parity Games
- A Parametrized Algorithm for Matroid Branch-Width
- Mathematical Foundations of Computer Science 2005
- Logic for Programming, Artificial Intelligence, and Reasoning
- Jungles, bundles, and fixed-parameter tractability
- Directed Rank-Width and Displit Decomposition
- Finding Branch-Decompositions and Rank-Decompositions
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
