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 条
  • [1] Boliac R, 2002, LECT NOTES COMPUT SC, V2518, P44
  • [2] New graph classes of bounded clique-width
    Brandstadt, A
    Dragan, FF
    Le, HO
    Mosca, R
    [J]. THEORY OF COMPUTING SYSTEMS, 2005, 38 (05) : 623 - 645
  • [3] Clique-width for 4-vertex forbidden subgraphs
    Brandstaedt, Andreas
    Engelfriet, Joost
    Le, Hoang-Oanh
    Lozin, Vadim V.
    [J]. THEORY OF COMPUTING SYSTEMS, 2006, 39 (04) : 561 - 590
  • [4] On the relationship between clique-width and treewidth
    Corneil, DG
    Rotics, U
    [J]. SIAM JOURNAL ON COMPUTING, 2005, 34 (04) : 825 - 847
  • [5] Polynomial time recognition of Clique-width ≤3 graphs -: Extended abstract
    Corneil, DG
    Habib, M
    Lanlignel, JM
    Reed, B
    Rotics, U
    [J]. LATIN 2000: THEORETICAL INFORMATICS, 2000, 1776 : 126 - 134
  • [6] Linear time solvable optimization problems on graphs of bounded clique-width
    Courcelle, B
    Makowsky, JA
    Rotics, U
    [J]. THEORY OF COMPUTING SYSTEMS, 2000, 33 (02) : 125 - 150
  • [7] HANDLE-REWRITING HYPERGRAPH GRAMMARS
    COURCELLE, B
    ENGELFRIET, J
    ROZENBERG, G
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (02) : 218 - 270
  • [8] On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
    Courcelle, B
    Makowsky, JA
    Rotics, U
    [J]. DISCRETE APPLIED MATHEMATICS, 2001, 108 (1-2) : 23 - 52
  • [9] Upper bounds to the clique width of graphs
    Courcelle, B
    Olariu, S
    [J]. DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) : 77 - 114
  • [10] Espelage W., 2003, Journal of Graph Algorithms and Applications, V7, DOI 10.7155/jgaa.00065
123