Solving Vertex Cover Problem by Tissue P Systems with Cell Division
Solving Vertex Cover Problem by Tissue P Systems with Cell Division
复制标题
通过细胞分裂的组织 P 系统解决顶点覆盖问题
DOI：
10.12785/amis/080141
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tao Song, Hongjiang Zheng, Juanjuan He
中科院分区：
文献类型：
--
作者：
Tao Song, Hongjiang Zheng, Juanjuan He
组织P系统是在膜计算中研究的一类分布式并行计算模型，它的灵感来自于组织中通信细胞的结构和功能。这类具有细胞分裂（对应于活细胞的有丝分裂行为）的系统理论上可以在线性时间内产生指数工作空间，从而提供了一种可能的方法，通过时空权衡在可行时间内解决计算难题。本文构造了一族带细胞分裂的组织P系统来求解顶点覆盖问题，并得到了线性时间解（关于问题的大小）.此外，我们证明了系统是以统一的方式构造的，并以融合的方式工作。
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.
登录
查看更多内容
DOI：
10.1016/j.tcs.2008.12.055
发表时间：
2009-06
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Xingyi Zhang;Xiangxiang Zeng;L. Pan
通讯作者：
Xingyi Zhang;Xiangxiang Zeng;L. Pan
DOI：
10.1007/978-3-642-54239-8
发表时间：
2013
期刊：
--
影响因子：
--
作者：
A. Alhazov;Svetlana Cojocaru;Marian Gheorghe Yurii Rogozhin;Grzegorz Rozenberg Arto Salomaa
通讯作者：
A. Alhazov;Svetlana Cojocaru;Marian Gheorghe Yurii Rogozhin;Grzegorz Rozenberg Arto Salomaa
影响因子：
1.1
作者：
Martín-Vide, C;Paun, G;Rodríguez-Patón, A
通讯作者：
Rodríguez-Patón, A
影响因子：
--
作者：
G. Paun
通讯作者：
G. Paun
DOI：
10.1007/978-3-642-56196-2
发表时间：
2002-09
期刊：
--
影响因子：
--
作者：
G. Paun
通讯作者：
G. Paun