马红平[1]2002年在《最大团问题及其分支定界法研究》文中研究表明本文首先对当前国际上最大团问题的理论研究成果及算法研究中的启发式算法进行了介绍，然后对精确算法中的分支定界法作了较为详细的讨论，最后作者在现有算法的基础上，给出了最大加权团问题的一种新的分支定界算法。该算法用团的简单启发式算法提供下界；用加权着色的启发式算法提供上界；在分支阶段，每次只产生一个新的子问题，并利用着色信息来选择分支顶点；最后利用回溯法来检验整体最优性。该算法从理论上提供了减小搜索树的规模及运行时间的可能性。
续晓欣[2]2006年在《Q0-1规划模型下最大团、最大加权独立集问题的研究》文中研究表明图中的最大团问题与最大独立集问题均属于图论中经典的NP-完全问题，该类问题所具有的固有困难，已使其普遍有效算法的寻求变得希望渺茫。但由于该类问题深刻而广泛的理论及应用背景，寻求其尽可能有效的精确算法和近似算法，近年来仍是计算数学工作者们十分关注的课题。 本文首先介绍了最大团及最大加权独立集问题的数学含义及其关系。对该类问题在国内外研究现状的介绍，重点放在各种精确算法和启发式算法的思想以及基本算法流程方面。 本文进一步重点阐述了Q0-1规划模型 main f(X)=C~TX+1/2X~TQX，X∈{0,1}~n(其中Q=(q_η)_(n×n)是一个n×n阶的有理矩阵，C是一个n维有理向量)的背景及其一般形式，并具体介绍了求解该类模型使用的分支定界算法。上述模型和算法是本文模型和算法的基础。 在第叁、第四、第五章中，作者基于上述Q0-1规划模型提出了形式更为简洁的Q0-1规划模型，此种模型与原有模型相比，与图的基本不变量具有更直接对应关系，这一改进对建模过程的简化特别有效。在此模型基础上，本文首先针对非加权最大团问题给出其分支定界法的理论基础及算法步骤直至算法实例，其次，又针对最大加权独立集问题进一步
参考文献：
[1]. 最大团问题及其分支定界法研究[D]. 马红平. 太原理工大学. 2002
[2]. Q0-1规划模型下最大团、最大加权独立集问题的研究[D]. 续晓欣. 太原理工大学. 2006