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

代强强 等: 面向二部图的极大缺陷二团高效枚举算法 1801

Br C L \N(S R ) 的大小还可能小于 k. 在此情况下, 定理 1 将不再适用. 为了确保递归能够继
对于某个递归分支 ,
C L 中任意选择一个顶点 , 然后将递归分支
v
续进行, 本文针对此情况还设计了一种简单的分支技术, 其思想是从
v
v
划分为两个子分支 Br 1 与 Br 2 以分别枚举包含 与不包含 的极大 k-缺陷二团.
值得注意的时, 文献 [12] 中也使用了一种称之为对称集合枚举的技术以解决极大 k-biplex (定义如文献 [12]
所示) 的枚举问题, 其基本思想与图 2 一致. 然而, 针对极大 k-缺陷二团枚举问题, 本文提出的枚举策略与文献 [12]
中的方法具有较大差异. 具体而言, 文献 [12] 的方法首先从当前递归的搜索空间 (由候选集和当前解组成的诱导
子图) 中找出一个具有最小度的顶点 v, 然后基于顶点 v 是否存在于当前解中, 决定是否执行对称集合枚举技术.
而本文提出的方法 (如定理 1 所示), 主要基于当前解中的顶点在候选集中非共同邻居的个数来执行对称集合枚举
技术. 此外, 极大 k-biplex 的枚举问题可以基于最小度的大小提前终止当前递归, 但极大 k-缺陷二团枚举问题没有
类似的提前终止优化. 因此, 设计高效的极大 k-缺陷二团枚举算法相较于极大 k-biplex 的枚举问题更具挑战性.

3.2 算法实现

基于第 3.1 节中提出的分支方法, 本节将设计一种算法以枚举给定图中的极大 k-缺陷二团. 其具体的伪代码
如算法 1 所示.
L
算法 1. 基本枚举算法.

输入: 二部图 G , 正整数 k 与 q ⩾ k +1 ;
q 的极大 k-缺陷二团.
输出: 所有不小于
,
,
,
,
,
1. Branch( ∅ ∅ L R ∅ ∅ );
S L S R C L C R X L X R )
2. Function Branch( , , , , ,
3. if C L ∪C R = ∅ then
4. if X L ∪ X R = ∅∧|S L | ⩾ q∧|S R | ⩾ q then
5. 输出 (S L ,S R ) 为极大解;
6. end if
7. return;
8. end if
¯
;
9. D L = C L \N(S R ) = {v 1 ,...,v d L } D R = C R \N(S L ) = {u 1 ,...,u d R } s ← k −d(S L ,S R ) ;
;
10. if |D L | ⩾ s then
,
,
11. Branch( S L S R C L C R X L \{v 1 } X R );
,
,
,
12. for i = 2 to s then
′
13. S ← S L ∪{v 1 ,...,v i−1 } ;
L
C ← C L \{v 1 ,...,v i } X ← X L \{v i } ;
′
′
14. L ; L
′ ′ ′
15. 更新 C , C R X , X R 使其中任意顶点均可用于扩展当前解 (S ,S R ) ;
,
L L L
′
′
16. Branch( S ′ , S R C , C R X , X R );
,
,
L L L
17. end for
′
′
18. S ← S L ∪{v 1 ,...,v s } C ← C L \D L ;
;
L
′ ′ ′
19. 更新 C , C R X , X R 使其中任意顶点均可用于扩展当前解 (S ,S R ) ;
,
L
L
L
′
,
20. Branch( S ′ , S R C , C R X L X R );
,
,
L L
21. else if |D R | > s then
22. 用 D R 中的顶点执行 10–20 行;
23. else
′
;
24. C L ∪C R 中选择一个顶点 v , 假设 v ∈ C L S ← S L ∪{v} ;
L