title: An unenumerative DNA computing model for vertex coloring problem.
abstract: The solution space exponential explosion caused by the enumeration of the candidate solutions maybe is the biggest obstacle in DNA computing. In the paper, a new unenumerative DNA computing model for graph vertex coloring problem is presented based on two techniques: 1) ordering the vertex sequence for a given graph in such a way that any two consecutive labeled vertices i and i+1 should be adjacent in the graph as much as possible; 2) reducing the number of encodings representing colors according to the construture of the given graph. A graph with 12 vertices without triangles is solved and its initial solution space includes only 283 DNA strands, which is 0.0532 of 3(12) (the worst complexity).
authors: Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing, China. jxu@pku.edu.cn
authors: Jin
authors: J
authors: Xu
authors: Xiaoli
authors: X
authors: Qiang
authors: Yan
authors: Y
authors: Yang
authors: Baoju
authors: B
authors: Wang
authors: Dongliang
authors: D
authors: Yang
authors: Liang
authors: L
authors: Luo
authors: Linqiang
authors: L
authors: Pan
authors: Shudong
authors: S
authors: Wang
mesh_terms: D001483:Base Sequence; D003116:Color; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D039301:Computers, Molecular; D004247:DNA / Q000737:chemistry* / Q000378:metabolism; D015342:DNA Probes; D004587:Electrophoresis, Agar Gel; D008969:Molecular Sequence Data; D016133:Polymerase Chain Reaction
chemical_list: D015342:DNA Probes; D004247:DNA