Computing the clique-width of large path powers in linear time via a new characterisation of clique-width

DOI10.1007/978-3-642-20712-9_18MaRDI QIDQ3007630zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Udi Rotics

Publication date 17 June 2011

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20712-9_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Clique-width of path powers
• Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Polynomial-time recognition of clique-width 3 graphs

Cites work

• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating clique-width and branch-width
• Chordal bipartite graphs of bounded tree- and clique-width
• Clique-width is NP-complete
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• From Tree-Width to Clique-Width: Excluding a Unit Interval Graph
• Handle-rewriting hypergraph grammars
• Linear layouts measuring neighbourhoods in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• New graph classes of bounded clique-width
• On a disparity between relative cliquewidth and relative NLC-width
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the Relationship Between Clique-Width and Treewidth
• On the clique-width of some perfect graph classes
• Recent developments on graphs of bounded clique-width
• The relative clique-width of a graph
• Upper bounds to the clique width of graphs

Cited in

(5)

• Clique-width of path powers
• Clique-width with an inactive label
• A characterisation of clique-width through nested partitions
• Graph classes with and without powers of bounded clique-width
• A Complete Characterisation of the Linear Clique-Width of Path Powers

This page was built for publication: Computing the clique-width of large path powers in linear time via a new characterisation of clique-width

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