**D. DÍAZ-PERNIL, M. J. PÉREZ-JIMÉNEZ, A. RISCOS-NÚÑEZ, Á. ROMERO-JIMÉNEZ**
*Computational Efficiency of Cellular Division
in Tissue-like Membrane Systems*
**Abstract.** Tissue-like P systems with cell division are computing models
in the framework of membrane computing. They are inspired by the intercellular
communication and neuronal synaptics, their structures being formalized by
underlying graphs. As usual in membrane computing, division rules allow the
construction of an exponential workspace (described by the number of cells) in a
linear time. In this paper this ability is used for presenting a uniform
linear{time solution for the (NP–complete) Vertex Cover problem via a uniform
family of such systems. This solution is compared to other ones obtained in the
framework of cell-like membrane systems.
READ THE PDF |