Rank-width: algorithmic and structural results
From MaRDI portal
Publication:2403788
DOI10.1016/j.dam.2016.08.006zbMath1369.05175arXiv1601.03800OpenAlexW2296118781MaRDI QIDQ2403788
Publication date: 12 September 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.03800
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (19)
Intertwining Connectivities for Vertex-Minors and Pivot-Minors ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Subgraph complementation ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Tangle bases: Revisited ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Unnamed Item ⋮ Recent Progress on Well-Quasi-ordering Graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Scattered Classes of Graphs ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ The complexity of the vertex-minor problem ⋮ Comparing linear width parameters for directed graphs ⋮ Digraphs of Bounded Width ⋮ Partial complementation of graphs ⋮ The grid theorem for vertex-minors ⋮ Rank connectivity and pivot-minors of graphs ⋮ Tree Pivot-Minors and Linear Rank-Width
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree-depth and vertex-minors
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- Fundamentals of parameterized complexity
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- A note on exact algorithms for vertex ordering problems on graphs
- Graph minors. XX: Wagner's conjecture
- Rank-width and tree-width of \(H\)-minor-free graphs
- Boolean-width of graphs
- Excluded vertex-minors for graphs of linear rank-width at most \(k\)
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Testing branch-width
- Partitions versus sets: a case of duality
- The rank-width of the square grid
- Computing rank-width exactly
- A faster strongly polynomial time algorithm for submodular function minimization
- Submodular partition functions
- Graph minors. V. Excluding a planar graph
- Distance-hereditary graphs
- Isotropic systems
- Graphic presentations of isotropic systems
- Local complementation and interlacement graphs
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- \(k\)-NLC graphs and polynomial algorithms
- On the monotonicity of games generated by symmetric submodular functions.
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Linear rank-width and linear clique-width of trees
- Clique-width and edge contraction
- Handle-rewriting hypergraph grammars
- The rank-width of edge-coloured graphs
- Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
- Obstructions for linear rank-width at most 1
- Graphs of small rank-width are pivot-minors of graphs of small tree-width
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Vertex-minor reductions can simulate edge contractions
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- Graph minors. IV: Tree-width and well-quasi-ordering
- The branchwidth of graphs and their cycle matroids
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Rank-width of random graphs
- Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Number of Cliques in Graphs with a Forbidden Subdivision
- Excluding a bipartite circle graph from line graphs
- Matroid Pathwidth and Code Trellis Complexity
- Rank-Width and Well-Quasi-Ordering
- Graph minors. II. Algorithmic aspects of tree-width
- Greedy algorithm and symmetric matroids
- Transforming trees by successive local complementations
- The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
- Constructive algorithm for path-width of matroids
- A Faster Scaling Algorithm for Minimizing Submodular Functions
- Linear Layouts in Submodular Systems
- Approximating rank-width and clique-width quickly
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Relationship Between Clique-Width and Treewidth
- Fast matrix rank algorithms and applications
- Rank‐width is less than or equal to branch‐width
- Parameterized Algorithms
- Finding Branch-Decompositions and Rank-Decompositions
This page was built for publication: Rank-width: algorithmic and structural results
