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 条
  • [21] Clique-width of partner-limited graphs
    Vanherpe, JM
    DISCRETE MATHEMATICS, 2004, 276 (1-3) : 363 - 374
  • [22] Clique-width of countable graphs: a compactness property
    Courcelle, B
    DISCRETE MATHEMATICS, 2004, 276 (1-3) : 127 - 148
  • [23] Optimal Centrality Computations Within Bounded Clique-Width Graphs
    Guillaume Ducoffe
    Algorithmica, 2022, 84 : 3192 - 3222
  • [24] Clique-width of full bubble model graphs
    Meister, Daniel
    Rotics, Udi
    DISCRETE APPLIED MATHEMATICS, 2015, 185 : 138 - 167
  • [25] Eigenvalue location in graphs of small clique-width
    Furer, Martin
    Hoppen, Carlos
    Jacobs, David P.
    Trevisan, Vilmar
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 560 : 56 - 85
  • [26] Bounding clique-width via perfect graphs
    Dabrowski, Konrad K.
    Huang, Shenwei
    Paulusma, Daniel
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2019, 104 : 202 - 215
  • [27] Graphs of linear clique-width at most 3
    Heggernes, Pinar
    Meister, Daniel
    Papadopoulos, Charis
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (39) : 5466 - 5486
  • [28] Chordal bipartite graphs of bounded tree- and clique-width
    Lozin, V
    Rautenbach, D
    DISCRETE MATHEMATICS, 2004, 283 (1-3) : 151 - 158
  • [29] The NLC-width and clique-width for powers of graphs of bounded tree-width
    Gurski, Frank
    Wanke, Egon
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 583 - 595
  • [30] On powers of graphs of bounded NLC-width (clique-width)
    Suchana, Karol
    Todinca, Ioan
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) : 1885 - 1893
12345