Solving Vertex Cover Problem by Tissue P Systems with Cell Division
| Autor: | Tao Song, Juan-juan He, Hongjiang Zheng |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Numerical Analysis Cell division Computer science Applied Mathematics Vertex cover Structure (category theory) Decision problem Space (mathematics) Topology Quantitative Biology::Cell Behavior Computer Science Applications Exponential function Computational Theory and Mathematics Membrane computing Time complexity Analysis |
| Zdroj: | Applied Mathematics & Information Sciences. 8:333-337 |
| ISSN: | 2325-0399 1935-0090 |
| DOI: | 10.12785/amis/080141 |
| Popis: | Tissue P systems are a class of distributed and parallel computing models investigated in membrane computing, which are inspired from the structure and functioning of communication cells in tissues . Such systems with cell division (corresponding to the mitosis behavior of living cells) can theoretically generate exponential wor king space in linear time, therefore providing a possible way to solve computational hard problems in feasible time by a space-time trade-off. In this work, we construct a family of tissue P systems with cell division to solve the vertex cover problems, and achieve a linear tim e solution (with respect to the size of the problems). Furthermore, we prove that the systems are constructed in a uniform manner and work in a confluent way. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|