The rank-width of edge-coloured graphs
From MaRDI portal
Publication:2392245
DOI10.1007/s00224-012-9399-yzbMath1269.05036arXiv0709.1433OpenAlexW2950414403MaRDI QIDQ2392245
Michaël Rao, Mamadou Moustapha Kanté
Publication date: 1 August 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0709.1433
clique-widthrank-widthvertex-minorlocal complementation2-structureexcluded configurationsigma-symmetry
Related Items
Acyclic coloring parameterized by directed clique-width, Rank-width: algorithmic and structural results, Grammars and clique-width bounds from split decompositions, Parameterized complexity of envy-free resource allocation in social networks, Are there any good digraph width measures?, Classes of intersection digraphs with good algorithmic properties, Directed NLC-width, Well-quasi-ordering of matrices under Schur complement and applications to directed graphs, Digraph width measures in parameterized algorithmics, Faster algorithms for vertex partitioning problems parameterized by clique-width, Efficient computation of the oriented chromatic number of recursively defined digraphs, Several notions of rank-width for countable graphs, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Computations by fly-automata beyond monadic second-order logic, On width measures and topological problems on semi-complete digraphs, Comparing linear width parameters for directed graphs, Digraphs of Bounded Width, Finding Branch-Decompositions of Matroids, Hypergraphs, and More
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the model-checking of monadic second-order formulas with edge set quantifications
- Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
- Monadic second-order model-checking on decomposable matroids
- Basic notions of universal algebra for language theory and graph grammars
- Graph minors. XX: Wagner's conjecture
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Recent developments on graphs of bounded clique-width
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
- Graph operations characterizing rank-width
- Circle graph obstructions
- On the excluded minors for the matroids of branch-width \(k\)
- Branch-width and well-quasi-ordering in matroids and graphs.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Branch-width, parse trees, and monadic second-order logic for matroids.
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Approximating clique-width and branch-width
- Recognizability, hypergraph operations, and logical types
- Rank-width and vertex-minors
- The relative clique-width of a graph
- On the Boolean-Width of a Graph: Structure and Applications
- Are There Any Good Digraph Width Measures?
- Fusion in relational structures and the verification of monadic second-order properties
- Clique-Width is NP-Complete
- Rank-Width and Well-Quasi-Ordering
- On Digraph Width Measures in Parameterized Algorithmics
- Graph minors. II. Algorithmic aspects of tree-width
- Digraph Decompositions and Eulerian Systems
- Decomposition of Directed Graphs
- Unifying Two Graph Decompositions with Modular Decomposition
- The Tutte Polynomial for Matroids of Bounded Branch-Width
- Directed Rank-Width and Displit Decomposition
- Finding Branch-Decompositions and Rank-Decompositions
