BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Vizing's Theorem in Near-Linear Time [Oberseminar Discrete Optimiz
 ation]
DTSTART:20260126T171500Z
DTEND:20260126T181500Z
DTSTAMP:20260722T052500Z
UID:indico-event-565@math-events.uni-bonn.de
DESCRIPTION:Speakers: Sayan Bhattacharya (University of Warwick)\n\nVizing
 's theorem states that any simple graph with n nodes\, m edges and maximum
  degree D admits a proper edge coloring with D+1 colors. Vizing's proof\, 
 dating back to 1960s\, was algorithmic\, and showed that such a (D+1)-edge
  coloring can be computed in O(mn) time. \nIn this talk\, I will explain 
 how to compute a (D+1)-edge coloring in only O(m log D) time with high pro
 bability\, leading to a near-optimal algorithm for this fundamental graph 
 problem.\nJoint work with Sepehr Assadi\, Soheil Behnezhad\, Martin Costa\
 , Shay Solomon and Tiyani Zhang.\n \nThe Oberseminar takes place in the S
 eminarraum\, 1st floor. Participants are invited to have coffee or tea in 
 the lounge before.\n \n\nhttps://math-events.uni-bonn.de/event/565/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/565/
END:VEVENT
END:VCALENDAR