Are there any good digraph width measures?
DOI10.1016/J.JCTB.2015.09.001zbMATH Open1327.05136OpenAlexW1900846841MaRDI QIDQ896003FDOQ896003
Jan Obdržálek, Somnath Sikdar, Petr Hliněný, Joachim Kneis, Peter Rossmanith, Daniel Meister, Robert Ganian
Publication date: 11 December 2015
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2015.09.001
Recommendations
Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Distance in graphs (05C12) Positional games (pursuit and evasion, etc.) (91A24)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Graph searching and a min-max theorem for tree-width
- The directed subgraph homeomorphism problem
- Directed tree-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Digraph width measures in parameterized algorithmics
- Approximating clique-width and branch-width
- Directed path-width and monotonicity in digraph searching
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The dag-width of directed graphs
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2005
- Title not available (Why is that?)
- Algorithms - ESA 2003
- Digraph measures: Kelly decompositions, games, and orderings
- Some simplified NP-complete graph problems
- Quickly excluding a planar graph
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- How to draw a planar graph on a grid
- A Min-Max Theorem on Tournaments
- Treewidth: Characterizations, Applications, and Computations
- DAG-Width and Parity Games
- DAG-width
- Tree-width and the monadic quantifier hierarchy.
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- List-Coloring Squares of Sparse Subcubic Graphs
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On topological tournaments of order 4 in digraphs of outdegree 3
- The rank-width of edge-coloured graphs
- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
- Tournament minors
- Complexity of the network median problem on planar grids
- A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (17)
- Acyclic coloring parameterized by directed clique-width
- Computing the zig-zag number of directed graphs
- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
- Title not available (Why is that?)
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Digraphs of Bounded Width
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Embedding phylogenetic trees in networks of low treewidth
- Directed tree-width
- Comparing linear width parameters for directed graphs
- Digraph coloring and distance to acyclicity
- Directed width parameters on semicomplete digraphs
- Efficient algorithms for measuring the funnel-likeness of DAGs
- How to compute digraph width measures on directed co-graphs
- Faster algorithms for counting subgraphs in sparse graphs
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- Directed ear anonymity
This page was built for publication: Are there any good digraph width measures?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896003)
