Please use this identifier to cite or link to this item:
|Title:||Computing the Clique-width of Cactus Graphs||Authors:||JOSE RAYMUNDO MARCIAL ROMERO
JOSE ANTONIO HERNANDEZ SERVIN
JACOBO LEONARDO GONZALEZ RUIZ
|Keywords:||computing;clique-width;cactus graphs;info:eu-repo/classification/cti/7||Publisher:||ELSEVIER||Project:||328;||Description:||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.||Other Identifiers:||http://hdl.handle.net/20.500.11799/67667||Rights:||info:eu-repo/semantics/openAccess
|Appears in Collections:||Producción|
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.