Solving Vertex Cover Problem by Means of Tissue P Systems with Cell Separation | Zendy

Chunyan Lu | Zendy; Xingyi Zhang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Solving Vertex Cover Problem by Means of Tissue P Systems with Cell Separation

Author(s) -

Chunyan Lu,

Xingyi Zhang

Publication year - 2010

Publication title -

international journal of computers communications and control

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.422

H-Index - 33

eISSN - 1841-9844

pISSN - 1841-9836

DOI - 10.15837/ijccc.2010.4.2512

Subject(s) - vertex cover , vertex (graph theory) , membrane computing , cover (algebra) , exponential function , computer science , separation (statistics) , workspace , polynomial , time complexity , mathematics , combinatorics , mathematical optimization , algorithm , theoretical computer science , artificial intelligence , graph , mathematical analysis , robot , mechanical engineering , machine learning , engineering

Tissue P systems is a computing model in the framework of membrane computing inspired from intercellular communication and cooperation between neurons. Many different variants of this model have been proposed. One of the most important models is known as tissue P systems with cell separation. This model has the ability of generating an exponential amount of workspace in linear time, thus it allows us to design cellular solutions to NP-complete problems in polynomial time. In this paper, we present a solution to the Vertex Cover problem via a family of such devices. This is the first solution to this problem in the framework of tissue P systems with cell separation.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research