A Complete Characterisation of the Linear Clique-Width of Path Powers

DOI10.1007/978-3-642-02017-9_27MaRDI QIDQ3630209zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Charis Papadopoulos

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Clique-width of path powers
• On powers of graphs of bounded NLC-width (clique-width)
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Linear rank-width and linear clique-width of trees
• Linear rank-width and linear clique-width of trees
• A local characterization of bounded clique-width for line graphs
• On clique graphs with linear size
• Linear clique-width of bi-complement reducible graphs

Cited in

(11)

• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Comparing linear width parameters for directed graphs
• Linear rank-width and linear clique-width of trees
• Clique-width of path powers
• Linear clique-width for hereditary classes of cographs
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Neighbourhood-width of trees
• Graphs of linear clique-width at most 3
• Graph classes with and without powers of bounded clique-width

This page was built for publication: A Complete Characterisation of the Linear Clique-Width of Path Powers

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