论文部分内容阅读
图的划分问题（GPP）是具有广泛应用背景的典型NP-难解问题，高效启发式算法一直是该领域的研究热点．作为设计启发式算法的有力工具，GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷．文中采用构造偏移GPP实例的技巧，不仅在理论上证明了获取GPP的骨架是NP-难解的，并且利用一般GPP实例与偏移实例的关系，实现了骨架规模的提高．在此基础上，文中对于目前求解GPP问题最好的算法之一的IBS进行了改进，提出了基于偏移实例的IBS算法（BI—IBS）．算法BI—IBS首先构造偏移GPP实例，然后再利用局部最