Computing the Clique-Width on Series-Parallel Graphs

被引：0
作者：
Antonio Lopez-Medina, Marco [1 ]
Leonardo Gonzalez-Ruiz, J. [1 ]
Raymundo Marcial-Romero, J. [1 ]
Hernandez, J. A. [1 ]
机构：
[1] Univ Autonoma Estado Mexico, Fac Ingn, Toluca De Lerdo, Mexico
来源：
COMPUTACION Y SISTEMAS | 2022年 / 26卷 / 02期
关键词：
Graph theory; clique-width; tree-width; complexity; series-parallel;
D O I：
10.13053/CyS-26-2-4250
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The clique-width (cwd) is an invariant of graphs which, similar to other invariants like the tree-width (twd) establishes a parameter for the complexity of a problem. For example, several problems with bounded clique-width can be solved in polynomial time. There is a well known relation between tree-width and clique-width denoted as cwd(G) <= 3 center dot 2(twd(G)-1). Serial-parallel graphs have tree-width of at most 2, so its clique-width is at most 6 according to the previous relation. In this paper, we improve the bound for this particular case, showing that the clique-width of series-parallel graphs is smaller or equal to 5.
引用
收藏
页码：815 / 822
页数：8
相关论文
共 50 条
  • [41] Clique-width: Harnessing the power of atoms
    Dabrowski, Konrad K. K.
    Masarik, Tomas
    Novotna, Jana
    Paulusma, Daniel
    Rzazewski, Pawel
    [J]. JOURNAL OF GRAPH THEORY, 2023, 104 (04) : 769 - 810
  • [42] Constrained-Path Labellings on Graphs of Bounded Clique-Width
    Bruno Courcelle
    Andrew Twigg
    [J]. Theory of Computing Systems, 2010, 47 : 531 - 567
  • [43] Infinitely many minimal classes of graphs of unbounded clique-width
    Collins, A.
    Foniok, J.
    Korpelainen, N.
    Lozin, V.
    Zamaraev, V.
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 248 : 145 - 152
  • [44] Constrained-Path Labellings on Graphs of Bounded Clique-Width
    Courcelle, Bruno
    Twigg, Andrew
    [J]. THEORY OF COMPUTING SYSTEMS, 2010, 47 (02) : 531 - 567
  • [45] Clique-width of graphs defined by one-vertex extensions
    Rao, Michael
    [J]. DISCRETE MATHEMATICS, 2008, 308 (24) : 6157 - 6165
  • [46] NCE graph grammars and clique-width
    Glikson, A
    Makowsky, JA
    [J]. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2003, 2880 : 237 - 248
  • [47] Bounding the clique-width of H-free split graphs
    Brandstaedt, Andreas
    Dabrowski, Konrad K.
    Huan, Shenwei
    Paulusma, Daniel
    [J]. DISCRETE APPLIED MATHEMATICS, 2016, 211 : 30 - 39
  • [48] Edge dominating set and colorings on graphs with fixed clique-width
    Kobler, D
    Rotics, U
    [J]. DISCRETE APPLIED MATHEMATICS, 2003, 126 (2-3) : 197 - 221
  • [49] A FRAMEWORK FOR MINIMAL HEREDITARY CLASSES OF GRAPHS OF UNBOUNDED CLIQUE-WIDTH
    Brignall, R.
    Cocks, D.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (04) : 2558 - 2584
  • [50] Bounding the Clique-Width of H-Free Chordal Graphs
    Brandstaedt, Andreas
    Dabrowski, Konrad K.
    Huang, Shenwei
    Paulusma, Daniel
    [J]. JOURNAL OF GRAPH THEORY, 2017, 86 (01) : 42 - 77
12345