Surface- Based Computing Model of Maximum Independent Set Problem


Article Preview

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.



Advanced Materials Research (Volumes 328-330)

Edited by:

Liangchi Zhang, Chunliang Zhang and Zichen Chen






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




[1] L .M. Aleman: Molecular Computation of Solutions to Combinatorial Problems. Science (1994) , 266 (5187), p.1021.

[2] J. Xu and Zh. Bao: Neural networks and graph theory, Science in China, E. series, (2001)31 (6), p.533.

[3] R. P. Feynmam. In minaturization; Gilbart,D. H., Ed.; Reinhold: New York, (1961), p.282.

[4] Head T: Formal Language Theory and DNA: An Analysis of the General Capacity of Specific Recombinant Behaviors. Bull. Math. Biology, (1987), 49, p.737.

[5] S. Roweis, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, and L. Adleman: A sticker-based model for DNA computation. J. Comput. Biol. (1998). 5 (4), p.615.

DOI: 10.1089/cmb.1998.5.615

[6] Q.H. Liu, L.M. Wang and A.G. Fruto: DNA computing on surfaces. Nature , 2000, 403 (13), p.175.

[7] Zh. X . Yin , F.Y. Zhang and J. Xu: 0-1 Planning Problem Based on DNA Computing, Journal of Electronics & Information Technology (2003), 15 (1) , p.1. (in Chinese).

[8] M.R. Garey and D.S. Johnson: Computers and Intractability-A Guide to the Theory of NP-Completeness. (1979) Freeman, New York.

[9] J.A. Bondy. and U.S.R. Murty: Graph theory with applications. The Mecmillan Press LTD (1976), p.108.

[10] Q. Ouyang, P .D. Kaplan andS M . Liu, et al : DNA solution of the maximal clique problem. Science , (1997), 278 (17) , p.446.

[11] T. Head, G. Rozenberg and R.B. Bladergroen , et al: Computing with DNA by operating on plasmids. Biosystems , ( 2000) , 57(2), p.87.

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