On a disparity between relative cliquewidth and relative NLC-width

DOI10.1016/j.dam.2009.06.024zbMath1210.05163OpenAlexW2169976284MaRDI QIDQ972344

Ruth Urner, Haiko Müller

Publication date: 25 May 2010

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

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

zbMATH Keywords

characterisationexact algorithmNLC-widthcliquewidth

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Clique-width of path powers ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ A characterisation of clique-width through nested partitions

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-NLC graphs and polynomial algorithms
• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• On the relationship between NLC-width and linear NLC-width
• The relative clique-width of a graph
• Clique-width minimization is NP-hard
• Graphs of Linear Clique-Width at Most 3
• NLC-2 Graph Recognition and Isomorphism
• Compact Forbidden-Set Routing
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: On a disparity between relative cliquewidth and relative NLC-width