理通万物 学究天人

He understands all things and is a scholar of man and nature

南开大学史永堂教授应邀为我院作学术报告

发布时间: 2026-11-16| 浏览次数: 10

11月16日,我院特邀南开大学史永堂教授作题为《Covering, Packing and Reconfiguration: Hardness and Algorithms for Spanning Structures in Graphs and Digraphs》的学术报告,报告由统计与数据科学学院院长陈小平主持。

报告围绕图论中覆盖、打包与重构三类核心问题,聚焦图及有向图中生成结构的计算复杂性与高效算法设计,按照“实际应用—已有成果—最新进展—未来方向”的思路层层展开。

在覆盖问题方面,史永堂指出三路顶点覆盖问题是NP-完全的,并以地铁安检调度、传染病传播阻断等实际问题为例,阐明了该问题的建模价值,同时系统介绍了平面图上的近似算法,以及树状网络中基于标记法的优化策略。

在打包与重构方面,史永堂分析了将网络分解为边不相交生成子结构的需求与挑战,利用“Zigzag连通性”给出了反强连通性的多项式时间判定算法,同时他还探讨了生成树边交换重构的可行性及其辅助图连通性的判定问题。

交流环节,与会教师围绕研究成果的应用前景、算法的可扩展性等问题,与史永堂进行了深入而富有建设性的研讨。

本次报告内容前沿、逻辑清晰、案例充实,为我院教师开展数学理论与实际问题相结合的交叉研究提供了重要启发与方法借鉴。

史永堂,南开大学教授、博士生导师,教育部重大人才工程特聘教授。主要研究领域为图论与组合优化。曾获国家自然科学基金优秀青年科学基金项目、天津市杰出青年基金项目等资助,以及霍英东教育基金会青年科学奖二等奖、中国工业与应用数学学会应用数学青年科技奖、中国运筹学会青年科技奖等奖项。