Rivas-Eddy RNA二级结构图书嵌入分类的实现方法

• 作者: 丁克诠 高世乐
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 假结 RNA二级结构 书嵌入 点着色 团数 色数 完美图
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 博士论坛
• 页码范围: 20-23,72
• 页数: 5页
• 分类号: TP301.2|Q71|O157.6
• 字数: 5091字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.04.006

摘要

书嵌入数是对图进行分类的一个拓扑标准,通常来说,计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题.针对Rivas-Eddy(R&E)类中RNA分子的二级结构图,从二级结构图的语法出发,通过其交叉关系图的点着色,构造性地得到了RNA分子二级结构图书嵌入的具体实现方法,完成了对RNA分子二级结构的书嵌入分类.该方法具有多项式时间复杂性,为求解NP完全问题提供了有益的参考.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高世乐	大连理工大学电子与信息工程学院	2	6	1.0	2.0
2	丁克诠	大连理工大学电子与信息工程学院	3	10	2.0	3.0