A linear-time tissue P system based solution for the 3-coloring problem

Díaz Pernil, Daniel; Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín

doi:10.1016/j.entcs.2007.05.009

Artículo

dc.creator	Díaz Pernil, Daniel	es
dc.creator	Gutiérrez Naranjo, Miguel Ángel	es
dc.creator	Pérez Jiménez, Mario de Jesús	es
dc.creator	Riscos Núñez, Agustín	es
dc.date.accessioned	2017-12-22T11:50:11Z
dc.date.available	2017-12-22T11:50:11Z
dc.date.issued	2007
dc.identifier.citation	Díaz Pernil, D., Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J. y Riscos Núñez, A. (2007). A linear-time tissue P system based solution for the 3-coloring problem. Electronic Notes in Theoretical Computer Science, 171 (2), 81-93.
dc.identifier.issn	1571-0661	es
dc.identifier.uri	http://hdl.handle.net/11441/67998
dc.description.abstract	In the literature, several examples of the efficiency of cell-like P systems regarding the solution of NPcomplete problems in polynomial time can be found (obviously, trading space for time). Recently, different new models of tissue-like P systems have received important attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3–coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems.	es
dc.description.sponsorship	Ministerio de Educación y Ciencia TIN2005-09345-C04-01	es
dc.description.sponsorship	Junta de Andalucía TIC-581	es
dc.format	application/pdf	es
dc.language.iso	eng	es
dc.publisher	Elsevier	es
dc.relation.ispartof	Electronic Notes in Theoretical Computer Science, 171 (2), 81-93.
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 Internacional	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/	*
dc.subject	Membrane Computing	es
dc.subject	Tissue P Systems	es
dc.subject	Cell division	es
dc.subject	3–coloring problem	es
dc.title	A linear-time tissue P system based solution for the 3-coloring problem	es
dc.type	info:eu-repo/semantics/article	es
dcterms.identifier	https://ror.org/03yxnpp24
dc.type.version	info:eu-repo/semantics/submittedVersion	es
dc.rights.accessRights	info:eu-repo/semantics/openAccess	es
dc.contributor.affiliation	Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial	es
dc.relation.projectID	TIN2005-09345-C04-01	es
dc.relation.projectID	TIC-581	es
dc.relation.publisherversion	http://www.sciencedirect.com/science/article/pii/S1571066107002800?via%3Dihub	es
dc.identifier.doi	10.1016/j.entcs.2007.05.009	es
dc.contributor.group	Universidad de Sevilla. TIC193: Computación Natural	es
idus.format.extent	13	es
dc.journaltitle	Electronic Notes in Theoretical Computer Science	es
dc.publication.volumen	171	es
dc.publication.issue	2	es
dc.publication.initialPage	81	es
dc.publication.endPage	93	es
dc.contributor.funder	Ministerio de Educación y Ciencia (MEC). España
dc.contributor.funder	Junta de Andalucía

Ficheros	Tamaño	Formato	Ver	Descripción
untitled.pdf	432.9Kb	[PDF]	Ver/Abrir

Este registro aparece en las siguientes colecciones

Artículos (Ciencias de la Computación e Inteligencia Artificial)

Mostrar el registro sencillo del ítem

Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional