Theory Seminar, Wednesday Jan 22: Shay Solomon (TAU) - Vizing's Theorem in Near-Linear Time

[Arnold Filtser]

Hi all,

Next week (Wed Jan 29, at 12) we will meet for our theory seminar. This will be the last talk for this semester

Location: Building 503 room 226.

See you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker:  Shay Solomon (TAU)
Title:  Vizing's Theorem in Near-Linear Time
Abstract:  Vizing's Theorem from 1964 states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ+1 different colors. Vizing's original proof is algorithmic and implies that such an edge coloring can be found in O(mn) time. In this talk, I'll present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time -- in fact, only O(mlogΔ) time -- with high probability.

[Arnold Filtser]

This happens tomorrow!