Paper Title:
Surface- Based Computing Model of Maximum Independent Set Problem
  Abstract

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 NP-complete 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 NP-complete problem.

  Info
Periodical
Advanced Materials Research (Volumes 328-330)
Chapter
Chapter 3: Mechatronics and Automation
Edited by
Liangchi Zhang, Chunliang Zhang and Zichen Chen
Pages
1729-1733
DOI
10.4028/www.scientific.net/AMR.328-330.1729
Citation
Y. Yang, Z. X. Yin, "Surface- Based Computing Model of Maximum Independent Set Problem", Advanced Materials Research, Vols. 328-330, pp. 1729-1733, 2011
Online since
September 2011
Export
Price
$32.00
Share

In order to see related information, you need to Login.

In order to see related information, you need to Login.

  | Authors: Heng Huang, Li Shen, James Ford, Yu Hang Wang, Yu Rong Xu
Abstract:Biomedical Nanotechnology is an emerging area of great scientific and technological opportunity. It is widely recognized as one of the most...
50
Authors: Lian Ye, Jing Chen, Yong Kang Xing
Abstract:DNA sequence design is the basic and important step for DNA computing. Good codeword could avoid some error may possibly occurred in...
94
Authors: Sheng Jun Xue, Wei Qi
Abstract:Traditional resource scheduling algorithm, in grid environment, exist some defects, for example it can not well meet the quality requirements...
1594
Authors: Guang Nian Yang, Wei Qi, Jun Zhou
Abstract:Now, our sewage treatment industry mainly depends on the blower of aeration act as metabolic, absorbed in the toxic substances. Blower...
591
Authors: Meng Jin, Xi Hui Mu, Liang Chun Li, Feng Po Du
Chapter 4: Organization of Manufacture, Engineering Management and Information Technologies
Abstract:Class-based stereo warehouse storage policy distributes products among a number of classes and for each class it reserves a region within the...
459