Computing the Clique-width of Cactus Graphs

Please use this identifier to cite or link to this item: http://ri.uaemex.mx/handle20.500.11799/67667

DC Field	Value	Language
dc.contributor.author	JOSE RAYMUNDO MARCIAL ROMERO	en_EU
dc.contributor.author	JOSE ANTONIO HERNANDEZ SERVIN	en_EU
dc.contributor.author	JACOBO LEONARDO GONZALEZ RUIZ	en_EU
dc.creator	JOSE RAYMUNDO MARCIAL ROMERO	-
dc.creator	JOSE ANTONIO HERNANDEZ SERVIN	-
dc.creator	JACOBO LEONARDO GONZALEZ RUIZ	-
dc.date	2016-01	-
dc.identifier	http://hdl.handle.net/20.500.11799/67667	-
dc.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.	-
dc.language	eng	-
dc.publisher	ELSEVIER	-
dc.relation	328;	-
dc.rights	info:eu-repo/semantics/openAccess	-
dc.rights	http://creativecommons.org/licenses/by-nc/4.0	-
dc.source	1571-0661	-
dc.subject	computing	-
dc.subject	clique-width	-
dc.subject	cactus graphs	-
dc.subject	info:eu-repo/classification/cti/7	-
dc.title	Computing the Clique-width of Cactus Graphs	-
dc.type	article	-
dc.audience	students	-
dc.audience	researchers	-
item.fulltext	No Fulltext	-
item.grantfulltext	none	-
Appears in Collections:	Producción

Check

DSpace CRIS