欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
骨架分析是近年来理论计算机科学研究的热点，对于NP-难解问题的启发式算法设计具有重要意义．由于骨架计算复杂性研究十分困难，现有的骨架分析方法多采用实验统计手段．针对现有方法中存在的骨架规模小的缺陷，给出图的二分问题GBP（graph bi-partitioning problem）的唯一全局最优解实例构造算法，有效提高了骨架的规模．同时，利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题，即在P≠NP的假设下，不存在多项式时间的算法可以确保得到GBP问题的完整骨架．本文的工作拓广了骨架计算复杂性研究的范围，所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值．
同期刊论文项目
同项目期刊论文
期刊信息
位置：