2017-12-262017-12-262008Dí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.0304-3975http://hdl.handle.net/11441/68003Several 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.application/pdfengAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Membrane ComputingTissue P SystemsCell division3–coloring probleminfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccess10.1016/j.tcs.2008.04.0056651346