The NLC-width and clique-width for powers of graphs of bounded tree-width

DOI10.1016/j.dam.2008.08.031zbMath1173.05342OpenAlexW2069832663MaRDI QIDQ1028448

Frank Gurski, Egon Wanke

Publication date: 30 June 2009

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

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

zbMATH Keywords

clique-widthtree-widthleaf powersNLC-widthtree powersSteiner powers

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Parameterized complexity of distance labeling and uniform channel assignment problems, A polynomial kernel for 3-leaf power deletion, Recognizing k -Leaf Powers in Polynomial Time, for Constant k, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Computing square roots of trivially perfect and threshold graphs, Unnamed Item, On low rank-width colorings, Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems, Linear rank-width and linear clique-width of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Structure and linear time recognition of 3-leaf powers
• Strictly chordal graphs are leaf powers
• Graph minors. I. Excluding a forest
• \(k\)-NLC graphs and polynomial algorithms
• Computing roots of graphs is hard
• On simple characterizations of k-trees
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On powers of graphs of bounded NLC-width (clique-width)
• Some remarks about leaf roots
• Vertex disjoint paths on clique-width bounded graphs
• On the relationship between NLC-width and linear NLC-width
• On Graph Powers for Leaf-Labeled Trees
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• On (k,ℓ)-Leaf Powers
• Graph minors. II. Algorithmic aspects of tree-width
• Graph Classes: A Survey
• Algorithms for Square Roots of Graphs
• Structure and linear-time recognition of 4-leaf powers
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Linear-Time Algorithms for Tree Root Problems
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science