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

被引：3

作者：

江贺 ^{[1
]}

张宪超 ^{[1
]}

陈国良 ^{[2
]}

机构：

[1] 大连理工大学软件学院

[2] 中国科学技术大学计算机科学与技术系

来源：

科学通报 | 2007年 / 17期

关键词：

图的二分问题; NP-难解; 骨架分析; 唯一全局最优解实例; 计算复杂性;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

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

引用

页码：2077 / 2081

页数：5

共 8 条

[1] 求解TSP问题的多级归约算法 [J].