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

DOI10.1016/j.tcs.2005.05.018zbMath1080.68086MaRDI QIDQ2576869

Frank Gurski, Egon Wanke

Publication date: 29 December 2005

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

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

zbMATH Keywords

clique-width; NLC-width; linear clique-width; NLCT-width; linear NLC-width

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, A local characterization of bounded clique-width for line graphs, Characterizations for restricted graphs of NLC-width 2, Linear layouts measuring neighbourhoods in graphs, The relative clique-width of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Complement reducible graphs
• \(k\)-NLC graphs and polynomial algorithms
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On a property of the class of n-colorable graphs
• The relative clique-width of a graph
• A Linear Recognition Algorithm for Cographs
• Graph minors. II. Algorithmic aspects of tree-width
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Graph Classes: A Survey
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Graph-Theoretic Concepts in Computer Science