Título

Computing the Clique-width of Cactus Graphs

Autor

JOSE RAYMUNDO MARCIAL ROMERO

JOSE ANTONIO HERNANDEZ SERVIN

JACOBO LEONARDO GONZALEZ RUIZ

Nivel de Acceso

Acceso Abierto

Resumen o descripción

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.

Editor

ELSEVIER

Fecha de publicación

enero de 2016

Tipo de publicación

Artículo

Fuente

1571-0661

Idioma

Inglés

Relación

328;

Audiencia

Estudiantes

Investigadores

Repositorio Orígen

REPOSITORIO INSTITUCIONAL DE LA UAEM

Descargas

227

Comentarios



Necesitas iniciar sesión o registrarte para comentar.