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

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

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

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Díaz Pernil, Daniel
Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús
Riscos Núñez, Agustín
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2007
Publicado en: Electronic Notes in Theoretical Computer Science, 171 (2), 81-93.
Tipo de documento: Artículo
Resumen: 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.
Cita: 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.
Tamaño: 432.9Kb
Formato: PDF

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

DOI: 10.1016/j.entcs.2007.05.009

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones