软件学报

作者：代强强，于瀚文，李荣华，李振军，王国仁

单位：代强强，北京理工大学 计算机学院, 北京 10008111,于瀚文，北京理工大学 计算机学院, 北京 10008102,李荣华，北京理工大学 计算机学院, 北京 100081;深圳城市职业技术学院 信息与通信学院, 广东 深圳 51803803,李振军，深圳城市职业技术学院 信息与通信学院, 广东 深圳 51803804,王国仁，北京理工大学 计算机学院, 北京 10008105

关键词：二部图;稠密子图挖掘;k-缺陷二团

基金：新一代人工智能国家科技重大专项(2020AAA0108503); 国家自然科学基金(U2241211, 62072034); 中国博士后创新人才支持计划(BX20240467); 中国博士后科学基金(2023M740245); 广东省哲学社会科学规划项目(GD21CYj21); 深圳市教育科学“十四五”规划: 2023年度项目(rgzn23021)

极大二团枚举问题是二部图分析中的一个基本研究问题. 然而, 在实际应用中, 传统二团模型要求子图必须为完全二部图的约束往往过于严格, 因此需要一些更为宽松的二团模型作为代替. 为此, 提出一种新的称之为k-缺陷二团的松弛二团模型. 该模型允许二部图子图与完全子图二团最多相差k条边. 由于极大k-缺陷二团枚举问题属于NP-难问题, 设计高效的枚举算法是一项极具挑战性的任务. 为解决此问题, 提出一种基于对称集合枚举的算法. 该算法的思想是通过k-缺陷二团中缺失边的数量约束来控制子分支的数量. 为进一步提高计算效率, 还提出一系列优化技术, 包括基于排序的子图划分方法、基于上界的剪枝方法、基于线性时间的更新技术以及分支的优化方法. 此外, 提出的优化算法的时间复杂度与${\\mathrm{O}}(\\gamma _k^n) $有关, 其中${\\gamma _k} \\lt 2 $, 突破了传统${\\mathrm{O}}({2^n}) $的时间复杂度. 最后, 大量的实验结果表明, 在大部分参数条件下所提方法的效率相较于传统分支定界方法提高了100倍以上.

来源：2025年第4期

《软件学报》期刊编辑部

查看软件学报杂志2025年第4期