Computing the Clique-width of Cactus Graphs

详细信息    查看全文

• 作者：J. Leonardo Gonzá ; lez-Ruiz¹ ; ^{leon.g.ruiz@gmail.com} ; J. Raymundo Marcial-Romero ^{jrmarcialr@uaemex.mx} ; J.A. Herná ; ndez-Serví ; n ^{xoseahernandez@uaemex.mx}
• 关键词：Graph theory ; Clique-width ; Tree-width ; Complexity
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2016
• 出版时间：8 December 2016
• 年：2016
• 卷：328
• 期：Complete
• 页码：47-57
• 全文大小：247 K
• 卷排序：328

文摘

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)−1cwd(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.