TCS+ talk *this week*: Wednesday, December 4, Martín Costa, University of Warwick
Clement Canonne
This is a reminder that the last TCS+ talk of the season is taking place this week, Wednesday, December 4th at 10:30 AM Eastern Time (7:30 AM Pacific Time, 16:30 Central European Time, 15:30 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks before the talk starts.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Martín Costa (University of Warwick)
Title: Vizing's Theorem in Near-Linear Time
Abstract: Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be edge colored using at most $\Delta + 1$ different colors [Vizing, 1964]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in $O(mn)$ time. This was improved to $\tilde O(m\sqrt{n})$ time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].
Very recently, independently and concurrently, this runtime bound was further improved to $\tilde{O}(n^2)$ by [Assadi, 2024] and $\tilde O(mn^{1/3})$ by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to $\tilde O(mn^{1/4})$ time by [Bhattacharya, Costa, Solomon and Zhang, 2024]).
In this talk, we present an algorithm that computes a $(\Delta+1)$-edge coloring in near-linear time -- in fact, only $O(m\log{\Delta})$ time -- giving a near-optimal algorithm for this fundamental problem.
Clement Canonne
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow, starting at 10:20am ET:
https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09 (you will need a to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>
Sent: Monday, December 2, 2024 10:04 PM
To: tcsplus_...@googlegroups.com
Subject: TCS+ talk *this week*: Wednesday, December 4, Martín Costa, University of Warwick
Hello everyone,
This is a reminder that the last TCS+ talk of the season is taking place this week, Wednesday, December 4th at 10:30 AM Eastern Time (7:30 AM Pacific Time, 16:30 Central European Time, 15:30 UTC). The speakers' slides will be made available at https://url.au.m.mimecastprotect.com/s/xydfCZY1NqiozJoQ6uzfEIBHyhx?domain=sites.google.com before the talk starts.
If you’d like to join the Zoom talk, please sign up using the form at https://url.au.m.mimecastprotect.com/s/dh9fC1WLPxcE8VEq4uGhvIVWC-h?domain=sites.google.com. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: https://url.au.m.mimecastprotect.com/s/TKRuC2xMQziE7ME8YuBi2I5q61s?domain=youtube.com.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Martín Costa (University of Warwick)
Title: Vizing's Theorem in Near-Linear Time
Abstract: Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be edge colored using at most $\Delta + 1$ different colors [Vizing, 1964]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in $O(mn)$ time. This was improved to $\tilde O(m\sqrt{n})$ time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].
Very recently, independently and concurrently, this runtime bound was further improved to $\tilde{O}(n^2)$ by [Assadi, 2024] and $\tilde O(mn^{1/3})$ by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to $\tilde O(mn^{1/4})$ time by [Bhattacharya, Costa, Solomon and Zhang, 2024]).
In this talk, we present an algorithm that computes a $(\Delta+1)$-edge coloring in near-linear time -- in fact, only $O(m\log{\Delta})$ time -- giving a near-optimal algorithm for this fundamental problem.
--
You received this message because you are subscribed to the Google Groups "TCS+" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus_announ...@googlegroups.com.
To view this discussion visit https://url.au.m.mimecastprotect.com/s/QV7fC3QNPBiRZnR2kFDsLIQxzrj?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/6ZW3C4QOPEi7rX7lVuVt5I4FTSm?domain=groups.google.com.