Translator Disclaimer
30 October 2006 DNA algorithm of minimal spanning tree
Author Affiliations +
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).
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Zhixiang Yin, Linqiang Pan, and Xiaohong Shi "DNA algorithm of minimal spanning tree", Proc. SPIE 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation, 63584O (30 October 2006);

Back to Top