A P system for finding all solutions of the vertex cover problem

doi:10.1166/jctn.2015.4505

	A P system for finding all solutions of the vertex cover problem
	Guo, Ping 1,3; Zhong, Yuwen 1; Chen, Haizhu2 ; Liu, Ran 1,3
	2015
发表期刊	Journal of Computational and Theoretical Nanoscience
ISSN	1546-1955
卷号	12 期号:12 页码:5229-5235
摘要	Vertex cover problem (VCP for short) is a kind of classical NP complete problems, and it is widely used in the fields of traffic signal system, very-large-scale integration research etc. Membrane computing, also called P systems, is biologically motivated theoretical model of distributed parallel computing. Finding all of vertex cover with size of κ is called All-VCP problem (κ is a given integer and not larger than the number of the vertices of the graph). At present, the algorithms to solve the Minimum vertex cover problem are more common, and they can find out all of satisfying vertex covers. There are several of P systems have been designed to solve VCP, but they can only answer whether there exists a vertex cover in a graph. In this paper, we propose a method to determine a vertex cover and design a P system to solve All-VCP problem based on this method. What's more, those vertex covers with size less than κ can also be found out. Our work provides a new and effective method to solve All-VCP problem in a distributed and parallel manner. Copyright © 2015 American Scientific Publishers All rights reserved.
关键词	Bioinformatics Computational complexity Distributed computer systems Problem solving Signal systems Traffic signals All-VCP Distributed parallel computing Finding all solutions Membrane computing Minimum vertex cover problems P systems Vertex cover Vertex Cover problems
DOI	10.1166/jctn.2015.4505
收录类别	EI
语种	英语
出版者	American Scientific Publishers
EI入藏号	20163202694066
EI分类号	432.4 Highway Traffic Control ; 461.8.2 Bioinformatics ; 721.1 Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory ; 722.4 Digital Computers and Systems ; 921.4 Combinatorial Mathematics, Includes Graph Theory, Set Theory
原始文献类型	Journal article (JA)
文献类型	期刊论文
条目标识符	https://ir.cqcet.edu.cn/handle/39TD4454/2933
专题	人工智能与大数据学院
作者单位	1.College of Computer Science, Chongqing University, Chongqing; 400030, China; 2.Department of Software Engineering, Chongqing College of Electronic Engineering, Chongqing; 401331, China; 3.Chongqing Key Laboratory of Software Theory and Technology, Chongqing; 400044, China
推荐引用方式 GB/T 7714	Guo, Ping,Zhong, Yuwen,Chen, Haizhu,et al. A P system for finding all solutions of the vertex cover problem[J]. Journal of Computational and Theoretical Nanoscience,2015,12(12):5229-5235.
APA	Guo, Ping,Zhong, Yuwen,Chen, Haizhu,&Liu, Ran.(2015).A P system for finding all solutions of the vertex cover problem.Journal of Computational and Theoretical Nanoscience,12(12),5229-5235.
MLA	Guo, Ping,et al."A P system for finding all solutions of the vertex cover problem".Journal of Computational and Theoretical Nanoscience 12.12(2015):5229-5235.