The NLC-width and clique-width for powers of graphs of bounded tree-width
From MaRDI portal
Publication:1028448
DOI10.1016/j.dam.2008.08.031zbMath1173.05342OpenAlexW2069832663MaRDI QIDQ1028448
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
Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (9)
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
This page was built for publication: The NLC-width and clique-width for powers of graphs of bounded tree-width
