当前位置: 首页 | 学术交流 | 学术交流 | 正文

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

信息来源:   发布日期: 2022-05-27  浏览次数:

报告人:郁星星教授

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

腾讯会议ID:248678121

报告主题:Approximating TSP walks in subcubic graphs

主  办:数学与统计学院、离散数学及其应用省部共建教育部重点实验室

报告摘要:

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等国际知名学术网站都对该项成果进行了报道。