p.1713

p.1717

p.1721

p.1725

p.1729

p.1734

p.1739

p.1743

p.1747

# 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:

Main Theme:

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 and 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

Authors:

Price:

$35.00

Permissions: