BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Anton Bernshteyn (Carnegie Mellon University)
DTSTART:20200629T130000Z
DTEND:20200629T140000Z
DTSTAMP:20260423T052450Z
UID:EPC/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/EPC/12/">A f
 ast distributed algorithm for $(\\Delta + 1)$-edge-coloring</a>\nby Anton 
 Bernshteyn (Carnegie Mellon University) as part of Extremal and probabilis
 tic combinatorics webinar\n\n\nAbstract\nA celebrated theorem of Vizing sa
 ys that every graph $G$ of maximum degree $\\Delta$ is $(\\Delta+1)$-edge-
 colorable. In this talk I will describe a deterministic distributed algori
 thm in the LOCAL model that finds a $(\\Delta+1)$-edge-coloring in the num
 ber of rounds that is polynomial in $\\Delta$ and $\\log n$\, where $n = |
 V(G)|$. This is the first distributed algorithm for $(\\Delta + 1)$-edge-c
 oloring with running time better than $O(\\mathrm{diameter}(G))$.\n
LOCATION:https://researchseminars.org/talk/EPC/12/
END:VEVENT
END:VCALENDAR