On switching classes, NLC-width, cliquewidth and treewidth

DOI10.1016/J.TCS.2011.12.021MaRDI QIDQ418754zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hans L. Bodlaender, Jurriaan Hage

Publication date 30 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.12.021

zbMATH Keywords

graph decomposition

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• On a disparity between relative cliquewidth and relative NLC-width
• On the relationship between NLC-width and linear NLC-width
• Line graphs of bounded clique-width
• Graph-Theoretic Concepts in Computer Science
• The behavior of clique-width under graph operations and graph transformations

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• A Linear Recognition Algorithm for Cographs
• A partial k-arboretum of graphs with bounded treewidth
• Dynamic labeled 2-structures
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Experimental and Efficient Algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 107643 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• scientific article; zbMATH DE number 3225111 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the structure of node-label-controlled graph languages
• Parallel concepts in graph theory
• Upper bounds to the clique width of graphs

Cited in

(2)

• On the relationship between NLC-width and linear NLC-width
• Switching classes: characterization and computation

This page was built for publication: On switching classes, NLC-width, cliquewidth and treewidth

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