A Complete Characterisation of the Linear Clique-Width of Path Powers

被引：0

作者：

Heguernes, Pinar ^{[1
]}

Meister, Daniel ^{[1
]}

Papadopoulos, Charis ^{[2
]}

机构：

[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway

[2] Univ Loannina, Dept Math, Loannina, Greece

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION | 2009年 / 5532卷

关键词：

BOUNDED TREE-WIDTH; NLC-WIDTH; GRAPHS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A k-path power is the k-power graph of a simple path of arbitrary length. Path powers form a non-trivial subclass of proper interval graphs. Their clique-width is not bounded by a constant, and no polynomial-time algorithm is known for computing their clique-width or linear clique-width. We show that k-path powers above a certain size have linear clique-width exactly k + 2, providing the first complete characterisation of the linear clique-width of a graph class of unbounded clique-width. Our characterisation results in a simple linear-time algorithm for computing the linear clique-width of all path powers.

引用

页码：241 / +

页数：3

共 27 条

[11] Fellows M. R., 2006, STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, P354, DOI 10.1145/1132516.1132568
[12] FOMIN F, 2009, SODA 2009, P825
[13] Golumbic M. C., 2000, International Journal of Foundations of Computer Science, V11, P423, DOI 10.1142/S0129054100000260
[14] Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
Gurski, F
[J]. DISCRETE MATHEMATICS, 2006, 306 (02) : 271 - 277
[15] On the relationship between NLC-width and linear NLC-width
Gurski, F
Wanke, E
[J]. THEORETICAL COMPUTER SCIENCE, 2005, 347 (1-2) : 76 - 89
[16] Linear layouts measuring neighbourhoods in graphs
Gurski, Frank
[J]. DISCRETE MATHEMATICS, 2006, 306 (15) : 1637 - 1650
[17] The NLC-width and clique-width for powers of graphs of bounded tree-width
Gurski, Frank
Wanke, Egon
[J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 583 - 595
[18] Heggernes P., 2009, ELECT NOTES DISCRETE, V32, P27
[19] HEGGERNES P, 2007, 362 U BERG
[20] Heggernes P, 2008, LECT NOTES COMPUT SC, V4978, P330, DOI 10.1007/978-3-540-79228-4_29

← 1 2 3 →