Rank-width: algorithmic and structural results
From MaRDI portal
(Redirected from Publication:2403788)
Abstract: Rank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by `simple' cuts. This survey aims to summarize known algorithmic and structural results on rank-width of graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 4162893 (Why is no real title available?)
- scientific article; zbMATH DE number 4064479 (Why is no real title available?)
- scientific article; zbMATH DE number 3779513 (Why is no real title available?)
- scientific article; zbMATH DE number 15493 (Why is no real title available?)
- scientific article; zbMATH DE number 1472167 (Why is no real title available?)
- A Faster Scaling Algorithm for Minimizing Submodular Functions
- A c^k n 5-approximation algorithm for treewidth
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A faster strongly polynomial time algorithm for submodular function minimization
- A note on exact algorithms for vertex ordering problems on graphs
- Approximating clique-width and branch-width
- Approximating rank-width and clique-width quickly
- Boolean-width of graphs
- Branchwidth of graphic matroids
- Call routing and the ratcatcher
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- Clique-width and edge contraction
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Computing rank-width exactly
- Constructive algorithm for path-width of matroids
- Distance-hereditary graphs
- Excluded vertex-minors for graphs of linear rank-width at most \(k\)
- Excluding a bipartite circle graph from line graphs
- Fast matrix rank algorithms and applications
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Finding Branch-Decompositions and Rank-Decompositions
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- Fundamentals of parameterized complexity
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XX: Wagner's conjecture
- Graphic presentations of isotropic systems
- Graphs of small rank-width are pivot-minors of graphs of small tree-width
- Greedy algorithm and symmetric matroids
- Handle-rewriting hypergraph grammars
- Isotropic systems
- Linear layouts in submodular systems
- Linear rank-width and linear clique-width of trees
- Linear time solvable optimization problems on graphs of bounded clique-width
- Local complementation and interlacement graphs
- Matroid Pathwidth and Code Trellis Complexity
- Number of cliques in graphs with a forbidden subdivision
- Obstructions for linear rank-width at most 1
- On the Relationship Between Clique-Width and Treewidth
- On the clique-width of some perfect graph classes
- On the monotonicity of games generated by symmetric submodular functions.
- Parameterized algorithms
- Partitions versus sets: a case of duality
- Polynomial-time recognition of clique-width 3 graphs
- Rank-Width and Well-Quasi-Ordering
- Rank-width and tree-width of \(H\)-minor-free graphs
- Rank-width and vertex-minors
- Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
- Rank-width of random graphs
- Rank‐width is less than or equal to branch‐width
- Submodular partition functions
- Testing branch-width
- The branchwidth of graphs and their cycle matroids
- The rank-width of edge-coloured graphs
- The rank-width of the square grid
- The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
- Transforming trees by successive local complementations
- Tree-depth and vertex-minors
- Unifying duality theorems for width parameters in graphs and matroids (extended abstract)
- Upper bounds to the clique width of graphs
- Vertex-minor reductions can simulate edge contractions
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
- \(k\)-NLC graphs and polynomial algorithms
Cited in
(36)- The grid theorem for vertex-minors
- Tree pivot-minors and linear rank-width
- Thread graphs, linear rank-width and their algorithmic applications
- Approximating rank-width and clique-width quickly
- Rank connectivity and pivot-minors of graphs
- Monoidal Width: Capturing Rank Width
- The rank-width of the square grid
- Fast FPT-approximation of branchwidth
- Automata approach to graphs of bounded rank-width
- Intertwining Connectivities for Vertex-Minors and Pivot-Minors
- List k-colouring P_t-free graphs: a mim-width perspective
- Comparing linear width parameters for directed graphs
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Rank‐width is less than or equal to branch‐width
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Tangle bases: Revisited
- Scattered classes of graphs
- Recent progress on well-quasi-ordering graphs
- Graph operations characterizing rank-width
- Tree pivot-minors and linear rank-width
- Graphs of bounded depth‐2 rank‐brittleness
- Treewidth, Circle Graphs, and Circular Drawings
- Treewidth, circle graphs and circular drawings
- Distance from triviality 2.0: hybrid parameterizations
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- The complexity of the vertex-minor problem
- Partial complementation of graphs
- Rank-width and vertex-minors
- Computing rank-width exactly
- Directed rank-width and displit decomposition
- Vertex-minors of graphs: a survey
- On the complexity of finding large odd induced subgraphs and odd colorings
- Digraphs of bounded width
- Subgraph complementation
- Obstructions for linear rank-width at most 1
This page was built for publication: Rank-width: algorithmic and structural results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403788)
