Share Email Print
cover

Proceedings Paper

DNA algorithm of minimal spanning tree
Author(s): Zhixiang Yin; Linqiang Pan; Xiaohong Shi
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Minimum spanning tree is one of important problem in graph theory and has a variety of applications. Kruskal's adding edge and cutting cycle methods are routinely and commonly used method when finding a minimum spanning tree of a specific graph. However, the two methods require determining whether adding edge or cutting cycle will induce cycle at every step during the course of computation. This paper present a new method to solve the minimum spanning tree prblem by means of encoding the graph in DNA strands and employing conventional biological manipulations, such as, electrophoresis, sequencing,etc. The proposed method can avoid the drawback of Kruskal's methods, moreover, the time complexity of proposed method is Ο(n), and the amount of DNA strands required for encoding is m n + ( n is the number of vertices and m is the number of edges of the graph).

Paper Details

Date Published: 30 October 2006
PDF: 5 pages
Proc. SPIE 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation, 63584O (30 October 2006); doi: 10.1117/12.718220
Show Author Affiliations
Zhixiang Yin, Anhui Univ. of Science and Technology (China)
Huazhong Univ. of Science and Technology (China)
Linqiang Pan, Huazhong Univ. of Science and Technology (China)
Xiaohong Shi, Anhui Univ. of Science and Technology (China)


Published in SPIE Proceedings Vol. 6358:
Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation
Jiancheng Fang; Zhongyu Wang, Editor(s)

© SPIE. Terms of Use
Back to Top