On switching classes, NLC-width, cliquewidth and treewidth

DOI10.1016/J.TCS.2011.12.021zbMATH Open1242.05217DBLPjournals/tcs/BodlaenderH12OpenAlexW2077329115WikidataQ59567556 ScholiaQ59567556MaRDI QIDQ418754FDOQ418754

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

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

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)

Cites Work

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

Cited In (1)

• On the relationship between NLC-width and linear NLC-width

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)