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

作　　者：江贺[1] 张宪超[1] 陈国良[2] 

机构地区：[1]大连理工大学软件学院,大连116621 [2]中国科学技术大学计算机科学与技术系,合肥230027

出　　处：《科学通报》2007年第17期2077-2081,共5页Chinese Science Bulletin

基　　金：国家自然科学基金(批准号:60673046;60673066);辽宁省自然科学基金(批准号:20051082);大连理工大学青年教师培养基金资助项目

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

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

分 类 号：O157.5[理学—数学]