Repositorio de producción científica de la Universidad de Sevilla

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

 

Advanced Search
 
Opened Access A uniform family of tissue P systems with cell division solving 3-COL in a linear time
Cites

Show item statistics
Icon
Export to
Author: Díaz Pernil, Daniel
Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús
Riscos Núñez, Agustín
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2008
Published in: Theoretical Computer Science, 404 (1-2), 76-87.
Document type: Article
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.
Cite: 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.
Size: 1.459Mb
Format: PDF

URI: http://hdl.handle.net/11441/68003

DOI: 10.1016/j.tcs.2008.04.005

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)