团是图论中检测凝聚子图的重要概念之一，并广泛应用于人工智能和数据挖掘等领域。团要求其顶点间两两相邻，但是该限制条件在实际应用中过于严格，因此作为团的一种松弛形式，k-Plex允许其顶点之间存在边的缺失，在识别凝聚子图时起到了更重要的作用，近年来对k-Plex相关算法的研究受到了广泛的关注。在给定的图中寻找包含顶点数量最多的k-Plex，即最大k-Plex问题，是该领域的研究热点，同时为了更好的分析图的内在结构，极大k-Plex枚举算法也备受关注。近些年，针对上述k-Plex问题的算法被相继提出，并在社交网络分析、生物信息学等方向发挥了重要作用。
　　本文首先针对最大k-Plex问题，研究了分支限界算法中的启发式策略。提出了两种高效的分支顶点顺序启发式策略以加快搜索速度，一种是通过收集子图约减过程中的顶点历史信息，根据顶点的历史信息选择分支顶点；另一种则结合顶点历史信息和顶点的度进行分支顶点的选择。同时，本文还根据顶点的度提出了一种顶点约减程度的启发式策略从而避免无效约减和耗时。本文将所提出的启发式策略整合在分支限界算法中，并对这些启发式策略进行了验证，实验结果表明所提出的启发式策略对求解效率有显著的提升。
　　另一方面，对于极大k-Plex的枚举问题，本文结合多种约减规则设计了一个枚举极大连通k-Plex的分支限界算法，并提出两个剪枝规则从而避免了重复搜索不包含极大k-Plex的分支，同时对算法回溯阶段的约减过程进行了参数化设置，并利用参数优化工具irace对参数进行优化。一系列对比实验表明，本文所提出的枚举算法在计算效率上优于最近提出的k-Plex枚举算法。