Comparing linear width parameters for directed graphs
From MaRDI portal
Abstract: In this paper we introduce the linear clique-width, linear NLC-width, neighbourhood-width, and linear rank-width for directed graphs. We compare these parameters with each other as well as with the previously defined parameters directed path-width and directed cut-width. It turns out that the parameters directed linear clique-width, directed linear NLC-width, directed neighbourhood-width, and directed linear rank-width are equivalent in that sense, that all of these parameters can be upper bounded by each of the others. For the restriction to digraphs of bounded vertex degree directed path-width and directed cut-width are equivalent. Further for the restriction to semicomplete digraphs of bounded vertex degree all six mentioned width parameters are equivalent. We also show close relations of the measures to their undirected versions of the underlying undirected graphs, which allow us to show the hardness of computing the considered linear width parameters for directed graphs. Further we give first characterizations for directed graphs defined by parameters of small width.
Recommendations
Cites work
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- A Separator Theorem for Planar Graphs
- A complete axiomatisation for the inclusion of series-parallel partial orders
- A partial k-arboretum of graphs with bounded treewidth
- Algorithms for generalized vertex-rankings of partial k-trees
- Approximating clique-width and branch-width
- Are there any good digraph width measures?
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Classes of directed graphs
- Clique-width is NP-complete
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Complexity of Finding Embeddings in a k-Tree
- Computing directed pathwidth in O(1.89ⁿ) time
- Computing the pathwidth of directed graphs with small vertex cover
- Digraph searching, directed vertex separation and directed pathwidth
- Digraph width measures in parameterized algorithmics
- Digraphs
- Directed NLC-width
- Directed path-width and directed tree-width of directed co-graphs
- Directed path-width and monotonicity in digraph searching
- Directed tree-width
- Dynamic algorithms for graphs of bounded treewidth
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- From tree-decompositions to clique-width terms
- Fully dynamic recognition algorithm and certificate for directed cographs
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- Graph parameters measuring neighbourhoods in graphs-bounds and applications
- Graph structure and monadic second-order logic. A language-theoretic approach
- Graphs of linear clique-width at most 3
- Jungles, bundles, and fixed-parameter tractability
- Knapsack problems: a parameterized point of view
- Linear layouts in submodular systems
- Linear layouts measuring neighbourhoods in graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linear time solvable optimization problems on graphs of bounded clique-width
- Matroid Pathwidth and Code Trellis Complexity
- New graph classes of bounded clique-width
- Obstruction set isolation for the gate matrix layout problem
- On the clique-width of some perfect graph classes
- On the pathwidth of almost semicomplete digraphs
- On the relationship between NLC-width and linear NLC-width
- Optimal Linear Ordering
- Oriented threshold graphs
- Quantitative graph theory. Mathematical foundations and applications
- Rank-width and tree-width of \(H\)-minor-free graphs
- Rank-width and vertex-minors
- Rank-width: algorithmic and structural results
- Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
- The rank-width of edge-coloured graphs
- Thread graphs, linear rank-width and their algorithmic applications
- Tournament immersion and cutwidth
- Upper bounds to the clique width of graphs
- Vertex disjoint paths on clique-width bounded graphs
- \(k\)-NLC graphs and polynomial algorithms
Cited in
(9)- Directed NLC-width
- Acyclic coloring parameterized by directed clique-width
- On tradeoffs between width- and fill-like graph parameters
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- On characterizations for subclasses of directed co-graphs
- Directed width parameters on semicomplete digraphs
- Linear layouts measuring neighbourhoods in graphs
- Degreewidth: A New Parameter for Solving Problems on Tournaments
- Synchronizing series-parallel deterministic finite automata with loops and related problems
This page was built for publication: Comparing linear width parameters for directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322714)
