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

被引：35

作者：

Gurski, F ^{[1
]}

Wanke, E ^{[1
]}

机构：

[1] Univ Dusseldorf, Inst Comp Sci, D-40225 Dusseldorf, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 347卷 / 1-2期

关键词：

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

D O I：

10.1016/j.tcs.2005.05.018

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we consider NLC-width, NLCT-width, and linear NLC-width bounded graphs. We show that the set of all complete binary trees has unbounded linear NLC-width and that the set of all co-graphs has unbounded NLCT-width. Since trees have NLCT-width 3 and co-graphs have NLC-width 1, it follows that the family of linear NLC-width bounded graph classes is a proper subfamily of the family of NLCT-width bounded graph classes and that the family of NLCT-width bounded graph classes is a proper subfamily of the family of NLC-width bounded graph classes. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：76 / 89

页数：14