| 图顶点着色问题的DNA粘贴算法 |
| |
| 引用本文： | 王淑栋,刘文斌,许进.图顶点着色问题的DNA粘贴算法[J].系统工程与电子技术,2005,27(3):568-572. |
| |
| 作者姓名： | 王淑栋 刘文斌 许进 |
| |
| 作者单位： | 1. 山东科技大学信息科学与工程学院,山东,泰安,271019;华中科技大学控制科学与工程系,湖北,武汉,430074
2. 华中科技大学控制科学与工程系,湖北,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金资助课题(60274026，60174047) |
| |
| 摘 要： | 利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法解决了图顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。
|
| 关 键 词： | DNA粘贴模型 图顶点着色 顶点独立集 顶点划分 |
| 文章编号： | 1001-506X(2005)03-568-05 |
| 修稿时间： | 2004年3月29日 |
DNA sticker algorithm for vertex-coloring problems of graph |
| |
| WANG Shu-dong,LIU Wen-bin,XU Jin.DNA sticker algorithm for vertex-coloring problems of graph[J].System Engineering and Electronics,2005,27(3):568-572. |
| |
| Authors: | WANG Shu-dong LIU Wen-bin XU Jin |
| |
| Institution: | WANG Shu-dong~ |
| |
| Abstract: | Using the huge parallelism of DNA sticker models, we first decompose the vertex-coloring problems of graph into vertex-independent set problems and vertex-partition problems from the essence of problems and show DNA sticker algorithms of the two problems. Then we solve vertex-coloring problems of graph by transferring the two algorithms. |
| |
| Keywords: | DNA sticker model vertex-coloring of graph vertex-independent set vertex-partition |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
