{"id":4485,"date":"2021-12-02T02:30:03","date_gmt":"2021-12-02T07:30:03","guid":{"rendered":"http:\/\/matroidunion.org\/?p=4485"},"modified":"2021-12-09T23:49:30","modified_gmt":"2021-12-10T04:49:30","slug":"online-talk-michael-wigal","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=4485","title":{"rendered":"Online Talk: Michael Wigal"},"content":{"rendered":"\n<p><strong>Tuesday, Dec 7,<\/strong> <strong>3pm ET<\/strong> (8pm GMT, 9am Wed NZDT)<br \/><strong><a href=\"https:\/\/people.math.gatech.edu\/~mwigal3\/\">Michael Wigal<\/a><\/strong>, Georgia Tech<br \/><strong>Approximating TSP walks in subcubic graphs<\/strong><\/p>\n<div><strong>YouTube: <\/strong><a href=\"https:\/\/youtu.be\/UfxO1FcQ5X4\">https:\/\/youtu.be\/UfxO1FcQ5X4<\/a><\/div>\n<h5>\u00a0<\/h5>\n<h5><strong>Abstract:<\/strong><\/h5>\n<h5>We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $5n\/4 + n_2\/4 -1$, establishing a conjecture of Dvo\u0159\u00e1k, Kr\u00e1\u013e, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $5n\/4 + n_2\/4 -1$ (respectively, $5n\/4 &#8211; 2$). 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$.<\/h5>\n<h5><br \/>Joint work with Youngho Yoo and Xingxing Yu.<\/h5>\n","protected":false},"excerpt":{"rendered":"<p>Tuesday, Dec 7, 3pm ET (8pm GMT, 9am Wed NZDT)Michael Wigal, Georgia TechApproximating TSP walks in subcubic graphs YouTube: https:\/\/youtu.be\/UfxO1FcQ5X4 \u00a0 Abstract: We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices &hellip; <a href=\"https:\/\/matroidunion.org\/?p=4485\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":20,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11],"class_list":["post-4485","post","type-post","status-publish","format-standard","hentry","category-matroids","tag-online-talks"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4485","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4485"}],"version-history":[{"count":3,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4485\/revisions"}],"predecessor-version":[{"id":4497,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4485\/revisions\/4497"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4485"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4485"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4485"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}