报告题目: Covering, Packing and Reconfiguration: Hardness and Algorithms for Spanning Structures in Graphs and Digraphs
报告人:史永堂教授,南开大学
报告时间:2026年11月21日16:00-16:40
报告地点:腾讯会议:823-491-147
校内联系人:李勇 [email protected]
报告摘要: Networks raise three kinds of questions that share the same mathematics. Covering: where should a few monitors be placed so that nothing escapes their attention? Packing: can one network be split into several independent sub-networks that each still connect everything? Reconfiguration: how can a network be changed one link at a time without ever losing connectivity? We present one problem of each kind on graphs and digraphs, starting from the application and ending with our new results: a faster algorithm for the vertex cover P3 problem on tree-like graphs; the NP-completeness of a packing problem of Bang-Jensen, Bessy, Jackson and Kriesell, with efficient algorithms for well-connected and tree-like inputs; and the exact number of steps needed to reconfigure unions of spanning arborescences, answering a question of Kobayashi, Mahara and Schwarcz. Joint work with Jiangdong Ai, Zongwen Bai, Gregory Gutin, Hui Lei, Shasha Li and Jianhua Tu.
简介: 史永堂,南开大学教授、博导,主要研究领域是图论与组合优化。曾获国家自然科学基金优秀青年科学基金项目、天津市杰出青年基金项目等资助;霍英东教育基金会青年科学奖二等奖、中国工业与应用数学学会应用数学青年科技奖、中国运筹学会青年科技奖等。