Approximate the Clique-Width of a Graph Using Shortest Paths

dc.contributor.author	Gonzalez Ruiz, Leonardo
dc.contributor.author	Marcial Romero, J. Raymundo
dc.contributor.author	Hernandez Servin, J. A.
dc.contributor.author	De Ita, Guillermo
dc.date.accessioned	2022-02-26T06:58:51Z
dc.date.available	2022-02-26T06:58:51Z
dc.date.issued	2021-10-21
dc.identifier.issn	1611-3349
dc.identifier.uri	http://hdl.handle.net/20.500.11799/112775
dc.description	Articulo de Investigacion	es
dc.description.abstract	Abstract. In this paper, we present an algorithm to approximate the clique-width of a graph. The proposed approach is based on computing the shortest paths between pairs of vertices. We experimentally show that our proposal approximates the clique-width of simple graphs in polynomial time, while other methods that calculate it in an exact way, transform the problem to SAT, that is well-known as NP-Complete.	es
dc.description.sponsorship	CONACyT	es
dc.language.iso	eng	es
dc.rights	closedAccess	es
dc.rights.uri	http://creativecommons.org/licenses/by-nc/4.0	es
dc.subject	Graph theory · Clique-width · Algorithm complexity	es
dc.subject.classification	INGENIERÍA Y TECNOLOGÍA	es
dc.title	Approximate the Clique-Width of a Graph Using Shortest Paths	es
dc.type	Artículo	es
dc.provenance	Científica	es
dc.road	Verde	es
dc.organismo	Ingeniería	es
dc.ambito	Nacional	es
dc.cve.CenCos	20501	es
dc.cve.progEstudios	1009	es
dc.relation.vol	13068

Ficheros en el objeto digital

Nombre: 523088_1_En_Print ...

Tamaño: 226.6Kb

Formato: PDF

Descripción: Articulo principal

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)