Grammars and clique-width bounds from split decompositions

DOI10.1016/J.DAM.2019.07.001MaRDI QIDQ2174558zbMATH OpenOpenAlexWikidataFDO

Authors Bruno Courcelle

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

zbMATH Keywords

clique-widthdirected graphgraph grammargraph substitutionsplit decomposition

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• NCE graph grammars and clique-width.
• Directed rank-width and displit decomposition
• Solving some NP-complete problems using split decomposition
• Definable decompositions for graphs of bounded linear cliquewidth
• Definable decompositions for graphs of bounded linear cliquewidth

Cites work

• A calculus for the random generation of labelled combinatorial structures
• A characterisation of clique-width through nested partitions
• A survey of the algorithmic aspects of modular decomposition
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• An exact enumeration of distance-hereditary graphs
• Asymptotic enumeration of cographs
• Automata for the verification of monadic second-order graph properties
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Clique-width and edge contraction
• Clique-width is NP-complete
• Clique-width with an inactive label
• Computations by fly-automata beyond monadic second-order logic
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Decomposition of Directed Graphs
• Directed rank-width and displit decomposition
• Distance-hereditary graphs
• From tree-decompositions to clique-width terms
• Fundamentals of parameterized complexity
• Graph operations characterizing rank-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Linear time solvable optimization problems on graphs of bounded clique-width
• On quasi-planar graphs: clique-width and logical description
• On the clique-width of some perfect graph classes
• On the extension of bipartite to parity graphs
• On the model-checking of monadic second-order formulas with edge set quantifications
• Practical and efficient split decomposition via graph-labelled trees
• Rank-width and tree-width of \(H\)-minor-free graphs
• Rank-width and vertex-minors
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Structure and linear time recognition of 3-leaf powers
• The behavior of clique-width under graph operations and graph transformations
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• The rank-width of edge-coloured graphs

Cited in

(3)

• Graph decompositions for cartesian products
• scientific article; zbMATH DE number 3919851 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)

This page was built for publication: Grammars and clique-width bounds from split decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174558)