Comparing linear width parameters for directed graphs
From MaRDI portal
Publication:2322714
DOI10.1007/s00224-019-09919-xzbMath1420.05068arXiv1812.06653OpenAlexW2963793539WikidataQ128007649 ScholiaQ128007649MaRDI QIDQ2322714
Publication date: 5 September 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.06653
linear rank-widthgraph parameterslinear clique-widthneighbourhood-widthdirected path-widthlinear NLC-widthdirected threshold graphs
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20)
Related Items
Acyclic coloring parameterized by directed clique-width, Directed width parameters on semicomplete digraphs, Efficient computation of the oriented chromatic number of recursively defined digraphs, On characterizations for subclasses of directed co-graphs, Synchronizing series-parallel deterministic finite automata with loops and related problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing directed pathwidth in \(O(1.89^n)\) time
- Computing the pathwidth of directed graphs with small vertex cover
- Rank-width and tree-width of \(H\)-minor-free graphs
- Graphs of linear clique-width at most 3
- Tournament immersion and cutwidth
- New graph classes of bounded clique-width
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Are there any good digraph width measures?
- Directed NLC-width
- Digraph searching, directed vertex separation and directed pathwidth
- Graph parameters measuring neighbourhoods in graphs-bounds and applications
- Graph minors. I. Excluding a forest
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- A partial k-arboretum of graphs with bounded treewidth
- Obstruction set isolation for the gate matrix layout problem
- \(k\)-NLC graphs and polynomial algorithms
- Algorithms for generalized vertex-rankings of partial k-trees
- Dynamic algorithms for graphs of bounded treewidth
- Directed path-width and directed tree-width of directed co-graphs
- Directed tree-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- The rank-width of edge-coloured graphs
- Rank-width: algorithmic and structural results
- From tree-decompositions to clique-width terms
- Knapsack problems: a parameterized point of view
- Digraph width measures in parameterized algorithmics
- Approximating clique-width and branch-width
- Fully dynamic recognition algorithm and certificate for directed cographs
- Directed path-width and monotonicity in digraph searching
- Linear layouts measuring neighbourhoods in graphs
- Vertex disjoint paths on clique-width bounded graphs
- Rank-width and vertex-minors
- On the relationship between NLC-width and linear NLC-width
- Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
- Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Quantitative Graph Theory
- On the Pathwidth of Almost Semicomplete Digraphs
- Clique-Width is NP-Complete
- Matroid Pathwidth and Code Trellis Complexity
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- A Separator Theorem for Planar Graphs
- A complete axiomatisation for the inclusion of series-parallel partial orders
- Classes of Directed Graphs
- Oriented Threshold Graphs
- Linear Layouts in Submodular Systems
- Optimal Linear Ordering
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Digraphs
- Jungles, bundles, and fixed-parameter tractability
