Please use this identifier to cite or link to this item:
http://ri.uaemex.mx/handle20.500.11799/67667| 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 http://creativecommons.org/licenses/by-nc/4.0 |
| Appears in Collections: | Producción |
Show full item record
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.