Computing the Clique-width of Cactus Graphs

被引：1
|
作者：
Leonardo Gonzalez-Ruiz, J. [1 ]
Raymundo Marcial-Romero, J. [1 ]
Hernandez-Servin, J. A. [1 ]
机构：
[1] Univ Autonoma Estado Mexico, Fac Ingn, Toluca, Mexico
来源：
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2016年 / 328卷 / 328期
关键词：
Graph theory; Clique-width; Tree-width; Complexity;
D O I：
10.1016/j.entcs.2016.11.005
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Similar to the tree-width (twd), the clique-width (cwd) is an invariant of graphs. A well known relationship between tree-width and clique-width is that cwd(G) <= 3. 2(twd(G)) (1. I)t is also known that tree-width of Cactus graphs is 2, therefore the clique-width for those graphs is smaller or equal than 6. In this paper, it is shown that the clique-width of Cactus graphs is smaller or equal to 4 and we present a polynomial time algorithm which computes exactly a 4-expression.
引用
收藏
页码：47 / 57
页数：11
相关论文
共 50 条
  • [31] On quasi-planar graphs: Clique-width and logical description
    Courcelle, Bruno
    DISCRETE APPLIED MATHEMATICS, 2020, 278 : 118 - 135
  • [32] MSOL partitioning problems on graphs of bounded treewidth and clique-width
    Rao, Michael
    THEORETICAL COMPUTER SCIENCE, 2007, 377 (1-3) : 260 - 267
  • [33] Induced Minor Free Graphs: Isomorphism and Clique-Width
    Rémy Belmonte
    Yota Otachi
    Pascal Schweitzer
    Algorithmica, 2018, 80 : 29 - 47
  • [34] Induced Minor Free Graphs: Isomorphism and Clique-width
    Belmonte, Remy
    Otachi, Yota
    Schweitzer, Pascal
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2016, 9224 : 299 - 311
  • [35] On the linear structure and clique-width of bipartite permutation graphs
    Brandstädt, A
    Lozin, VV
    ARS COMBINATORIA, 2003, 67 : 273 - 281
  • [36] A local characterization of bounded clique-width for line graphs
    Gurski, Frank
    Wanke, Egon
    DISCRETE MATHEMATICS, 2007, 307 (06) : 756 - 759
  • [37] Clique-width of point configurations
    Cagirici, Onur
    Hlineny, Petr
    Pokryvka, Filip
    Sankaran, Abhisekh
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2023, 158 : 43 - 73
  • [38] The relative clique-width of a graph
    Lozin, Vadim
    Rautenbach, Dieter
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) : 846 - 858
  • [39] Clique-width: Harnessing the power of atoms
    Dabrowski, Konrad K. K.
    Masarik, Tomas
    Novotna, Jana
    Paulusma, Daniel
    Rzazewski, Pawel
    JOURNAL OF GRAPH THEORY, 2023, 104 (04) : 769 - 810
  • [40] CLIQUE-WIDTH IS NP-COMPLETE
    Fellows, Michael R.
    Rosamond, Frances A.
    Rotics, Udi
    Szeider, Stefan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (02) : 909 - 939
12345