A uniform family of tissue P systems with cell division solving 3-COL in a linear time

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.tcs.2008.04.005

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-26T09:51:27Z
dc.date.available	2017-12-26T09:51:27Z
dc.date.issued	2008
dc.identifier.citation	Díaz Pernil, D., Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J. y Riscos Núñez, A. (2008). A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science, 404 (1-2), 76-87.
dc.identifier.issn	0304-3975	es
dc.identifier.uri	http://hdl.handle.net/11441/68003
dc.description.abstract	Several examples of the efficiency of cell-like P systems regarding the solution of NPcomplete problems in polynomial time can be found in the literature(obviously, trading space for time). Recently, different new models of tissue-like P systems have received much 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	Theoretical Computer Science, 404 (1-2), 76-87.
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 uniform family of tissue P systems with cell division solving 3-COL in a linear time	es
dc.type	info:eu-repo/semantics/article	es
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/S030439750800251X?via%3Dihub	es
dc.identifier.doi	10.1016/j.tcs.2008.04.005	es
dc.contributor.group	Universidad de Sevilla. TIC193: Computación Natural	es
idus.format.extent	12	es
dc.journaltitle	Theoretical Computer Science	es
dc.publication.volumen	404	es
dc.publication.issue	1-2	es
dc.publication.initialPage	76	es
dc.publication.endPage	87	es
dc.identifier.sisius	6651346	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
QDQE=&response-content-disposi ...	1.459Mb	[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