Grammars and clique-width bounds from split decompositions
From MaRDI portal
Publication:2174558
DOI10.1016/j.dam.2019.07.001zbMath1437.05193OpenAlexW2963317407WikidataQ127493474 ScholiaQ127493474MaRDI QIDQ2174558
Publication date: 21 April 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2019.07.001
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- On the model-checking of monadic second-order formulas with edge set quantifications
- Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
- A survey of the algorithmic aspects of modular decomposition
- Clique-width with an inactive label
- Practical and efficient split decomposition via graph-labelled trees
- The behavior of clique-width under graph operations and graph transformations
- Rank-width and tree-width of \(H\)-minor-free graphs
- Structure and linear time recognition of 3-leaf powers
- Graph operations characterizing rank-width
- Distance-hereditary graphs
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- On the extension of bipartite to parity graphs
- A calculus for the random generation of labelled combinatorial structures
- Automata for the verification of monadic second-order graph properties
- Linear time solvable optimization problems on graphs of bounded clique-width
- On quasi-planar graphs: clique-width and logical description
- A characterisation of clique-width through nested partitions
- Clique-width and edge contraction
- The rank-width of edge-coloured graphs
- From tree-decompositions to clique-width terms
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Rank-width and vertex-minors
- Clique-Width is NP-Complete
- Decomposition of Directed Graphs
- An Exact Enumeration of Distance-Hereditary Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- Directed Rank-Width and Displit Decomposition
- Computations by fly-automata beyond monadic second-order logic
