Authors : Majid Darehmiraki and Hasan Mishmast Nehi
Abstract: DNA computing is new research areas in biology science and information science separately. The essential characteristic of it is the massive parallel of obtaining and managing information. It has been evidenced that DNA computing can solve those problems which are currently intractable on event the fastest electronic computers. The degree-constrained minimum spanning tree is an important problem in graph theory and it is an NP-complete problem. In this study, we present a algorithm for solving degree-constrained minimum spanning tree problem based on sticker model in DNA computing. The study finds all spanning trees of given graph and minimum spanning tree of given graph.
Majid Darehmiraki and Hasan Mishmast Nehi , 2007. A Parallel Algorithm for the Degree-Constrained Minimum Spanning Tree Problem by Using DNA Computing. Research Journal of Biological Sciences, 2: 658-662.