A characterisation of clique-width through nested partitions

DOI10.1016/J.DAM.2015.02.016MaRDI QIDQ2348055zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics, Bruno Courcelle

Publication date 10 June 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.02.016

zbMATH Keywords

characterisationclique-widthefficient representationlinear clique-width

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Graphs of linear clique-width at most 3
• A model-theoretic characterisation of clique width
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width

Cites work

• A survey of the algorithmic aspects of modular decomposition
• Approximating clique-width and branch-width
• 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
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Graph operations characterizing rank-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graphs of linear clique-width at most 3
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Linear layouts measuring neighbourhoods in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On a disparity between relative cliquewidth and relative NLC-width
• Parametrized complexity theory.
• The relative clique-width of a graph
• Upper bounds to the clique width of graphs

Cited in

(10)

• Optimal centrality computations within bounded clique-width graphs
• Maximum matching in almost linear time on graphs of bounded clique-width
• Grammars and clique-width bounds from split decompositions
• Clique-width of full bubble model graphs
• From tree-decompositions to clique-width terms
• A model-theoretic characterisation of clique width
• The relative clique-width of a graph
• Clique-width of path powers
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• The behavior of clique-width under graph operations and graph transformations

This page was built for publication: A characterisation of clique-width through nested partitions

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