Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950086 | Electronic Notes in Theoretical Computer Science | 2016 | 11 Pages |
Abstract
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â 2twd(G)â1. It 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J. Leonardo González-Ruiz, J. Raymundo Marcial-Romero, J.A. Hernández-ServÃn,