我院殷明浩教授指导的2024级博士研究生巫捷妤有两篇学术论文“ParaKplex: A Parallel Local Search Algorithm for the Maximum K-Plex Problem”和“A Parallel Framework for the Maximum Common Induced Subgraph Problem”分别被CCF A类期刊《Artificial Intelligence》和CCF B类会议IJCAI 2026接收。这两篇论文的第一作者为巫捷妤，通信作者为王艺源副教授，合作作者包括2022级博士生孙睿、2025级硕士生张权，博士后潘世维和高健教授。

随着组合优化问题的求解规模不断扩大，问题复杂度呈爆炸式增长，传统串行算法面临效率瓶颈。发展高性能并行计算方法以支撑大规模组合优化问题的求解，已成为当前亟待解决的关键问题。现有并行算法可划分为共享内存并行和分布式内存并行两类。围绕这一背景，研究团队聚焦于最大k-plex问题与最大公共子图问题这两类经典的图优化问题展开研究，分别设计了基于共享内存的k-plex求解算法和基于分布式内存的最大公共子图算法框架。首先，针对最大k-plex问题，设计并实现了一种并行局部搜索算法。该方法创新性地提出了一种基于分组的初始化机制，综合利用图的结构特征与历史搜索信息，在多线程间生成高质量的初始解。同时，设计了一种主辅搜索策略，有效引导算法在全局与局部搜索空间中交替探索。其次，针对最大公共子图问题，构建了一种通用的并行算法框架。该框架引入了基于搜索信息的动态任务分解方法，将模式顶点划分为优先匹配与排除匹配子集以有效划分任务，并辅以一种基于共享信息的剪枝策略，能有效剪枝冗余分支并引导搜索聚焦于有前景的子空间。实验结果表明，所提算法在最大k-plex和最大公共子图问题上均能显著提升求解质量与效率。