美国佐治亚理工大学郁星星教授学术报告

发布日期:2022-05-27    浏览次数:

报告主题:Approximating TSP walks in subcubic graphs

报告人: 郁星星教授

报告时间:20225309:00--12:00

腾讯会议ID248678121

邀请单位:88038威尼斯、离散数学及其应用省部共建教育部重点实验室

参加对象:感兴趣的老师和学生

报告摘要:

There has been extensive research on approximating TSP walks in subcubic graphs. We show that if G is a 2-connected simple subcubic graph on n vertices with m vertices of degree 2, then G has a TSP walk of length at most 5n/4+m/4-1, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible.  Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a 5/4-approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best-known approximation ratio of 9/7. This is joint work with Youngho Yoo and Michael Wigal.  


报告人简介:


郁星星,美国佐治亚理工大学(Georgia Institute of Technology)数学系教授。1990获美国Vanderbilt大学博士学位, 担任SIAM Journal of Discrete MathematicsDiscrete MathematicsJ. CombinatoricsSCIENCE CHINA Mathematics等多个国际杂志和有关学术机构的编委。主要研究领域为结构图论和图的算法,在国际知名杂志上发表论文100余篇,解决了图论中多个重要的猜想。最近,郁星星教授和其两位研究生证明了困扰离散数学领域图论界40年之久的Kelmans-Seymour猜想。Science DailySci24HBrunch NewsNewswisePHYS.ORG等国际知名学术网站都对该项成果进行了报道。


欢迎老师和同学们参加!