图的二分问题唯一全局最优解实例与骨架计算复杂性

• 作者: 张宪超 江贺 陈国良
• 来源期刊: 科学通报
• 学科: 化学
• 关键词: 图的二分问题 NP-难解 骨架分析 唯一全局最优解实例 计算复杂性
• 年，卷（期）: 2007,（17）
• 所属期刊栏目: 论文
• 页码范围: 2077-2081
• 页数: 5页
• 分类号: O6
• 字数: 5889字
• 语种: 中文
• DOI: 10.3321/j.issn:0023-074x.2007.17.017

摘要

骨架分析是近年来理论计算机科学研究的热点,对于NP-难解问题的启发式算法设计具有重要意义.由于骨架计算复杂性研究十分困难,现有的骨架分析方法多采用实验统计手段.针对现有方法中存在的骨架规模小的缺陷,给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法,有效提高了骨架的规模.同时,利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题,即在的假设下,不存在多项式时间的算法可以确保得到GBP问题的完整骨架.本文的工作拓广了骨架计算复杂性研究的范围,所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学与技术系	123	2142	20.0	43.0
2	张宪超	大连理工大学软件学院	29	428	12.0	20.0
3	江贺	大连理工大学软件学院	47	513	12.0	21.0