On a disparity between relative cliquewidth and relative NLC-width

DOI10.1016/J.DAM.2009.06.024zbMATH Open1210.05163OpenAlexW2169976284MaRDI QIDQ972344FDOQ972344

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

exact algorithmNLC-widthcharacterisationcliquewidth

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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

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