Computing the Clique-width of Cactus Graphs

dc.contributor.author	MARCIAL ROMERO, JOSE RAYMUNDO
dc.contributor.author	HERNANDEZ SERVIN, JOSE ANTONIO
dc.contributor.author	GONZALEZ RUIZ, JACOBO LEONARDO
dc.creator	MARCIAL ROMERO, JOSE RAYMUNDO; 39478
dc.creator	HERNANDEZ SERVIN, JOSE ANTONIO; 89146
dc.creator	GONZALEZ RUIZ, JACOBO LEONARDO; 502510
dc.date.accessioned	2017-11-13T23:19:38Z
dc.date.available	2017-11-13T23:19:38Z
dc.date.issued	2016-01
dc.identifier.issn	1571-0661
dc.identifier.uri	http://hdl.handle.net/20.500.11799/67667
dc.description.abstract	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.	es
dc.language.iso	eng	es
dc.publisher	ELSEVIER	es
dc.relation.ispartofseries	328;
dc.rights	openAccess	es
dc.rights.uri	http://creativecommons.org/licenses/by-nc/4.0
dc.subject	computing	es
dc.subject	clique-width	es
dc.subject	cactus graphs	es
dc.subject.classification	INGENIERÍA Y TECNOLOGÍA
dc.title	Computing the Clique-width of Cactus Graphs	es
dc.type	Artículo	es
dc.provenance	Científica	es
dc.road	Dorada	es
dc.ambito	Internacional	es
dc.audience	students
dc.audience	researchers
dc.type.conacyt	article
dc.identificator	7

Ficheros en el objeto digital

Nombre: 2016-ComputingCli ...

Tamaño: 247.2Kb

Formato: PDF

Los documentos depositados en el Repositorio Institucional de la Universidad Autónoma del Estado de México se encuentran a disposición en Acceso Abierto bajo la licencia Creative Commons: Atribución-NoComercial-SinDerivar 4.0 Internacional (CC BY-NC-ND 4.0)