%0 Journal Article
%T 图的二分问题唯一全局最优解实例与骨架计算复杂性
%A 江
%A 贺
%A 张宪超
%A 陈国良
%J 科学通报
%P 2077-2081
%D 2007
%X 骨架分析是近年来理论计算机科学研究的热点,对于NP-难解问题的启发式算法设计具有重要意义.由于骨架计算复杂性研究十分困难,现有的骨架分析方法多采用实验统计手段.针对现有方法中存在的骨架规模小的缺陷,给出图的二分问题GBP(graphbi-partitioningproblem)的唯一全局最优解实例构造算法,有效提高了骨架的规模.同时,利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题,即在P≠NP的假设下,不存在多项式时间的算法可以确保得到GBP问题的完整骨架.本文的工作拓广了骨架计算复杂性研究的范围,所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.
%K 图的二分问题
%K NP-难解
%K 骨架分析
%K 唯一全局最优解实例
%K 计算复杂性
%U http://csb.scichina.com:8080/CN/abstract/abstract370620.shtml