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
Materias
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
Recurso de información
Fuente
1571-0661
Idioma
Inglés
Relación
328;
Audiencia
Estudiantes
Investigadores
Repositorio Orígen
REPOSITORIO INSTITUCIONAL DE LA UAEM
Descargas
227