1. A Linear–time Tissue P System Based Solution for the 3–coloring Problem.
- Author
-
Díaz-Pernil, Daniel, Gutiérrez-Naranjo, Miguel A., Pérez-Jiménez, Mario J., and Riscos-Núñez, Agustín
- Subjects
CELLS ,NP-complete problems ,GRAPH theory ,BIOLOGY ,COMPUTATIONAL complexity - Abstract
Abstract: In the literature, several examples of the efficiency of cell-like P systems regarding the solution of NP-complete 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. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF