A characterisation of clique-width through nested partitions

DOI10.1016/j.dam.2015.02.016zbMath1315.05110OpenAlexW1995739513MaRDI QIDQ2348055

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

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-widthlinear clique-widthefficient representation

Mathematics Subject Classification ID

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

Related Items

Clique-width of path powers, Grammars and clique-width bounds from split decompositions, From tree-decompositions to clique-width terms, The behavior of clique-width under graph operations and graph transformations, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Optimal centrality computations within bounded clique-width graphs, Maximum matching in almost linear time on graphs of bounded clique-width, Clique-width of full bubble model graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• A survey of the algorithmic aspects of modular decomposition
• Graphs of linear clique-width at most 3
• On a disparity between relative cliquewidth and relative NLC-width
• Graph operations characterizing rank-width
• Automata for the verification of monadic second-order graph properties
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Clique-width and edge contraction
• Handle-rewriting hypergraph grammars
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• The relative clique-width of a graph
• A SAT Approach to Clique-Width
• Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
• Clique-Width is NP-Complete