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

TitleA linear-time tissue P system based solution for the 3-coloring problem
Publication TypeJournal Papers
Year of Publication2007
AuthorsDíaz-Pernil, D., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
Journal TitleElectronic Notes in Theoretical Computer Science
PublisherElsevier B.V.
Volume171
Pages81-93
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.

Keywords3-coloring problem, cell division, Membrane computing, Tissue P Systems
URLhttp://dx.doi.org/10.1016/j.entcs.2007.05.009
Issue2
DOI10.1016/j.entcs.2007.05.009