NLCT-width

• 2005 Gurski2005
  • page 8 : linear NLC-width $k$ upper bounds NLCT-width by $\mathcal O(k)$
  • page 8 : NLCT-width $k$ upper bounds NLC-width by $\mathcal O(k)$
  • page 8 : clique-tree-width $k$ upper bounds NLCT-width by $\mathcal O(k)$
  • page 8 : NLCT-width $k$ upper bounds clique-tree-width by $\mathcal O(k)$
  • page 8 : treewidth $k$ upper bounds NLCT-width by $f(k)$ – The results of [23] imply that each graph class of bounded path-width has bounded linear NLC-width and that each graph class of bounded tree-width has bounded NLCT-width.
• 1994 Wanke1994
  • page 4 : NLCT-width – Definition 2.2. Let $k \in \mathbb N$ be a positive integer. A \emph{$k$-node label controlled (NLC) tree} is a $k$-NL graph defined as follows: …