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 条

[31] On powers of graphs of bounded NLC-width (clique-width)
Suchana, Karol
Todinca, Ioan
DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) : 1885 - 1893
[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
Belmonte, Remy
Otachi, Yota
Schweitzer, Pascal
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2016, 9224 : 299 - 311
[34] Induced Minor Free Graphs: Isomorphism and Clique-Width
Rémy Belmonte
Yota Otachi
Pascal Schweitzer
Algorithmica, 2018, 80 : 29 - 47
[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] Treelength of series-parallel graphs?
Dissaux, Thomas
Ducoffe, Guillaume
Nisse, Nicolas
Nivelle, Simon
DISCRETE APPLIED MATHEMATICS, 2023, 341 : 16 - 30
[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

← 1 2 3 4 5 →