Page 398 - 《软件学报》2025年第4期

1804 软件学报 2025 年第 36 卷第 4 期

v 从候选
;
中 id 为顶点 u 的编号, 表示为 u.id nnd 为顶点 u 在 (S L ,S R ) 中的非邻居数量, 表示为 u.nnd . 基于该结构, 当
v
集中加入 (S L ,S R ) 时, 只需利用 与候选集中其他顶点 u 是否是邻居关系以及 v.nnd 与 u.nnd 的大小即可确定顶点 u
是否可以扩展新的当前解. 基于该思想, 本文设计了一种新的更新算法, 其伪代码如算法 2 所示. 容易看出其时间复
杂度与候选集的大小线性相关, 因为判断 (v.id,u.id) 是否是图 G 中的边可以基于索引技术在线性时间内完成.
算法 2. Update(S L ,v,S R ,C L ,C R ) .

¯
d(S L ,S R ) ← G(S L ,S R ) 中缺失的边数;
1.
′
′
;
2. C ← ∅ C ← ∅ ;
L R
3. foreach u ∈ C L then
¯
4. if d(S L ,S R )+v.nnb+u.nnb ⩽ k then
′
5. C .push(u) ;
L
6. end if
7. end for
8. foreach u ∈ C R then
9. if (v.id,u.id) < E then u.nnb ← u.nnb+1 ; end if
¯
10. if d(S L ,S R )+v.nnb+u.nnb ⩽ k then
′
11. C .push(u) ;
R
12. end if
13. end for
(C ,C ) ;
′
′
14. return L R
值得注意的是算法 2 仅展示了顶点 v 加入 S L 时更新候选集 (C L ,C R ) 的方法, 而排除集 (X L ,X R ) 的更新方法与
此类似. 同时当 v 加入 S R 时, 候选集与排除集的更新方法与 v 加入 S L 时也是类似的. 为了避免重复, 本文省略了针
对上述情况的更新方法.

4.4 分支优化技术 (X L ,X R ) 中存在顶点
在当前递归分支无法利用定理 1 来产生子递归分支时, 算法 1 将使用传统的分支定界技术以保证递归的继
续. 然而该方法的效率很低, 可能产生大量的冗余分支. 本文发现, 在执行分支定界技术过程中, 若用于扩展候选集
(S L ,S R ) 的顶点 能够使得新的当前解在候选集中具有更多的非邻居, 则可以提升枚举算法的性能. 因为当前解
v
(S L ,S R ) 在候选集中的非邻居数量越多, 不仅能够减少分支定界枚举的使用, 而且还有利于提高对称集合枚举的效
率. 为此, 当递归分支不满足定理 1 的要求时, 本文将从候选集 (C L ,C R ) 中选择在 G(S L ∪C L ,S R ∪C R ) 中度数最小的
顶点执行分支定界枚举.
除了上述提到的, 在算法 1 的 Branch 函数中, 本文还发现可以利用排除集中的顶点来判断当前递归是否可以
(S L ,S R ) 的 k-缺
提前终止, 以进一步减少冗余计算. 其主要思想是, 如果能够确定当前搜索空间中任何包含当前解
陷二团在原始二部图中一定不是极大的, 则当前递归可以直接终止计算. 为此, 可以得到如下结论.
定理 8. 在某个递归分支中, 若排除集 v ∈ X L (或者 u ∈ X R ) 满足 (S R ∪C R ) ⊆ N v (G) (或者
(S L ∪C L ) ⊆ N u (G) ), 则当前搜索空间中不存在极大解.
(A,B) 是当前递归搜索到的极大 (S L ∪C L ) ⊆ N u (G) ), 可
证明: 设 k-缺陷二团, 基于条件 (S R ∪C R ) ⊆ N v (G) (或者
以容易看出 (A∪{v},B) (或者 (A,B∪{u}) ) 一定是一个更大的 k-缺陷二团. 因此, 该递归分支中的任何解都不是极大的.
综合上述所有的优化技术, 可以得到一种改进的极大 k-缺陷二团枚举算法, 其具体的伪代码如算法 3 所示. 具
体的, 算法 3 首先基于排序优化将原始二部图划分成一系列的子图 ≻ ≻ ) (第 1–3 行), 然后利用上界剪
v i v i ,E v i
G = (L ,R v i
枝技术以减少子图的规模 (第 4 行), 最后在各个子图中调用 Branch 函数 (第 5 行) 枚举极大 k-缺陷二团. 值得注意
的是, 递归调用 Branch 加入了上界剪枝技术、线性更新技术以及分支优化技术.