Title :
A Novel DNA-Based Parallel Computation for Solving Graph Coloring Problems
Author :
Yeh, Chung-Wei ; Wu, Kee-Rong
Author_Institution :
Dept. of Manage. Inf. Syst., Kao Yuan Univ., Kaohsiung, Taiwan
Abstract :
This study provided molecular solutions for the graph coloring problems (GCP) by two steps: (1) translating vertices to strands and (2) generating DNA procedures. At the first step, we defined strands to present the vertices of graph; on the second step, we applied DNA parallel approach to construct algorithms. DNA computation takes use DNA molecules and biological operations to solve problems in a solution of DNA, where specific combination of DNA is interpreted as a particular result to a problem encoded by molecular. Based on the bio-operation proposed by Adleman and Amos, the proposed approach solves the 3-coloring and k-coloring problems with potential time complexity of O(nXk2), where n and k denote the number of vertices of graph G and the smallest positive number to color G, respectively.
Keywords :
biocomputing; computational complexity; graph colouring; parallel algorithms; DNA computing; DNA molecular solution; DNA procedure generation; DNA-based parallel computation algorithm; GCP; NP-complete problem; biological operation; graph k-coloring problem solving; graph vertex translation; time complexity; Biological information theory; Biology computing; Bonding; Concurrent computing; DNA computing; Management information systems; NP-complete problem; Polymers; Sequences; Software engineering; DNA Computing; NP-complete problem; graph coloring; k-coloring problem;
Conference_Titel :
Software Engineering, 2009. WCSE '09. WRI World Congress on
Conference_Location :
Xiamen
Print_ISBN :
978-0-7695-3570-8
DOI :
10.1109/WCSE.2009.267