近日，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队在理论计算机科学领域CCF A类顶级期刊《Information and Computation》上连续发表三篇高水平研究论文，充分展现了团队在该领域的突出科研实力与国际学术影响力。

《Information and Computation》自1957年创刊以来，始终秉持严格的学术标准与高要求的录用政策，是CCF推荐A类期刊中理论计算机科学方向的权威刊物。该刊每年发文量通常不超过100篇（除两年特例外），发表难度极高。据文献[黄铁军，我国计算机科学国际期刊论文状况，中国计算机学会通讯，11(8)2015]统计，该期刊是国内学者发表数量最少的CCF A类期刊之一。此次算法与逻辑团队连续三篇论文被该刊录用，标志着我校在理论计算机科学前沿研究领域取得重要突破。

第一篇论文题为“Exponential time algorithms for deciding regular games”（判定正则博弈的指数时间算法），第一作者为梁子辉博士，指导老师Bakh教授与肖鸣宇教授分别为第二、第三作者。论文链接：https://www.sciencedirect.com/science/article/pii/S0890540126000416

该论文聚焦反应系统分析与综合中的关键问题，系统研究了彩色Muller博弈、Rabin博弈等多类重要正则博弈模型。作者综合运用递归、动态规划等方法，创新性地引入子博弈编码分析技术，构建了统一的判定算法框架，将多类正则博弈的求解复杂度由超指数时间成功降至指数时间，显著提升了相关问题的理论求解效率，为反应系统的自动化验证与综合提供了新的理论工具。本文首次将彩色Muller博弈问题的求解复杂度从超指数时间降低至指数时间。相关结果的对比在图1中给出。

第二篇论文题为“Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k”（突破3^k界限：Co-Path/Cycle Packing与Co-Path Packing问题的快速求解），第一作者为刘雨曦博士，指导老师肖鸣宇教授为第二作者。论文链接：https://www.sciencedirect.com/science/article/pii/S0890540126000040

该工作针对生物信息学中的重要图问题——Co-Path/Cycle Packing与Co-Path Packing，提出了突破性的参数化算法。研究结合路径分解、动态规划、Cut & Count技术及分支搜索方法，成功将Co-Path/Cycle Packing的确定性算法时间复杂度突破3^k的瓶颈，为相关图结构问题的算法设计与分析提供了重要技术参考。本文算法与已有结果的对比由图2给出。

第三篇论文题为“Improved Approximations for the Capacitated Vehicle Routing Problem with Fixed Capacity”（固定容量车辆路径问题的改进近似算法），第一作者为赵景阳博士，指导老师肖鸣宇教授为第二作者。论文链接：https://www.sciencedirect.com/science/article/abs/pii/S0890540126000039

该论文深入研究了组合优化领域的经典核心难题——容量限制车辆路径问题（CVRP）。针对单位需求、可分需求与不可分需求三种重要变体，作者提出了一系列新型近似算法，大幅改进了该问题原有的近似比理论界限。本文算法与已知最优算法的对比由图3给出。由图3可见，该工作在车辆容量固定且较小的情形下取得了显著突破。以单位需求和可分需求CVRP为例，相较于此前文献中的最佳结果，团队提出的新算法在各项容量参数下均实现了近似比的全面降低（图中加粗部分为本研究所取得的最优结果）。尤其在容量k=3,4,5等小容量场景下，近似比的优化尤为明显。在近似算法领域，近似比数值的降低意味着算法在“最坏情况”下给出的调度方案成本更加逼近理论上的绝对最优解。该研究不仅在理论计算机科学的经典路径分配问题上取得了实质性突破，也为现实世界中的物流配送调度、无人机载货路线规划以及具有严格载重限制的运输场景，提供了具有更优最坏情况保障的理论基础与算法支撑。