{"id":34,"date":"2025-06-11T13:10:08","date_gmt":"2025-06-11T13:10:08","guid":{"rendered":"https:\/\/taaresearchlunch.univie.ac.at\/?p=34"},"modified":"2025-06-11T13:10:08","modified_gmt":"2025-06-11T13:10:08","slug":"22-may-2025-martin-costa","status":"publish","type":"post","link":"https:\/\/taaresearchlunch.univie.ac.at\/?p=34","title":{"rendered":"22 May 2025 &#8211; Martin Costa"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><strong>Date:<\/strong> 22 May 2025<br><strong>Time:<\/strong> 11:45 \u2013 12:45<br><strong>Location: <\/strong>Forschungslabor 3 (sofa room)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Speaker:<\/strong> Martin Costa<br><strong>Title:<\/strong> Vizing&#8217;s Theorem in Near-Linear Time<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><br>Vizing&#8217;s theorem states that any n-vertex m-edge graph of maximum degree \u0394 can be edge colored using at most \u0394 + 1 different colors [Vizing, 1964]. Vizing&#8217;s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to O\u0303(mn^(1\/2)) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Very recently, this runtime bound was further improved to O\u0303(n^2) by [Assadi et al., 2024] and O\u0303(mn^(1\/4)) by [Bhattacharya et al., 2024].<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In this talk, I will present a randomized algorithm that computes a (\u0394 + 1)-edge coloring in near-linear time\u2014in fact, only O(m log \u0394) time\u2014with high probability, giving a near-optimal algorithm for this fundamental problem.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Date: 22 May 2025Time: 11:45 \u2013 12:45Location: Forschungslabor 3 (sofa room) Speaker: Martin CostaTitle: Vizing&#8217;s Theorem in Near-Linear Time Abstract:Vizing&#8217;s theorem states that any n-vertex m-edge&#46;&#46;&#46;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-34","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/34","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=34"}],"version-history":[{"count":1,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/34\/revisions"}],"predecessor-version":[{"id":35,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/34\/revisions\/35"}],"wp:attachment":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=34"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=34"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}