报告主题：Approximating TSP walks in subcubic graphs

报告人： 郁星星教授

报告时间：2022年5月30日9:00--12:00

腾讯会议ID：248678121

邀请单位：数学与统计学院、离散数学及其应用省部共建教育部重点实验室

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

报告摘要：

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 Mathematics，Discrete Mathematics，J. Combinatorics，SCIENCE CHINA Mathematics等多个国际杂志和有关学术机构的编委。主要研究领域为结构图论和图的算法，在国际知名杂志上发表论文100余篇，解决了图论中多个重要的猜想。最近，郁星星教授和其两位研究生证明了困扰离散数学领域图论界40年之久的Kelmans-Seymour猜想。Science Daily、Sci24H、Brunch News、Newswise、PHYS.ORG等国际知名学术网站都对该项成果进行了报道。

欢迎老师和同学们参加！