Chinese Journal of Computers   Full Text
Title	Analysis for Graph Coloring Problem Based on Sticker and Deletion Systems
Authors	WANG Shu-Dong
Address	(College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266510) (School of Electronics Engineering and Computer Science, Peking University, Beijing 100871)
Year	2008
Issue	No.12(2123—2128)
Abstract &   Background	Abstract Graph coloring problem is a NP-complete one of graph and combinatorial optimization. The computational time increases exponentially with the size of the researched problem solved using the usual methods. Thus it is impossible to settle it efficiently. Sticker system and deletion system are the language generated mechanisms based on sticking and deleting operations respectively. In this paper, graph coloring problem was combined with the number of bad edges and transformed into a problem of searching for the longest sequence. On the basis, the chromatic number and all the color classes of graph were obtained using the parallelism of two formal models: sticker system and deletion system. Compared with the existing DNA algorithm for graph coloring problem, the proposed algorithm is of lower complexity. Keywords DNA computing; graph coloring; sticker and deletion systems; bad edge