Surface- Based Computing Model of Maximum Independent Set Problem
About thirty years ago, the concept of the complexity of the problem was proposed. The most important complex class is P and NP class. Fruitful results of this concept are the existence of the so-called complex class complete problem. If the other issues of this class once solved in polynomial time, then the problem must exist polynomial time algorithms. Therefore, the complete problem is most difficult to solve, but because of their presence, we can choose any of them improved algorithm for a problem, so this kind of problem to get a good solution. DNA computing is a novel method that solving a class of intractable computational problems, in which the computing speeds up exponentially with the problem size. Up to now, many accomplishments have been made to improve its performance and increase its reliability. Maximum Independent Set problem (MIS) is a well-known NPcomplete problem. Maximum Clique and Minimum Vertex Covering problem is equivalent to Maximum Independent Set problem. In this paper, we explore solving Maximum Independent Set problem by transforming it into equivalent 0-1 programming problem, and utilizing the surface computing model of that. The proposed method demonstrates universal nature of NPcomplete problem.
DNA Computing 0-1 Programming Problem Maximum Independent Set Maximum Clique Minimum Vertex Covering
Yan YANG Zhixiang YIN
Department of Control Science and Engineering, Huazhong University of Science and Technology Wuhan, Department of Mathematics and Physics, Anhui University of Science and Technology Huainan,China
国际会议
2011 International Conference on Mechatronics and Materials Processing(2011年机电一体化与材料加工国际会议 ICMMP)
广州
英文
1729-1733
2011-11-18（万方平台首次上网日期，不代表论文的发表时间）