BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Recent Advances in Vertex Connectivity Problems [Lecture]
DTSTART:20251111T080000Z
DTEND:20251111T084500Z
DTSTAMP:20260308T035600Z
UID:indico-event-889@math-events.uni-bonn.de
DESCRIPTION:Speakers: Sorrachai Yingchareonthawornchai\n\nVertex connectiv
 ity is a classic graph-theoretic notion that roughly measures the robustne
 ss of a graph against node failures. A classic open problem\, asked by Aho
 \, Hopcroft\, and Ullman in 1975\, is whether or not vertex connectivity c
 an be computed in linear time. Despite a lot of research effort in the pas
 t decades\, state-of-the-art algorithms were far from being linear time.  
 In this talk\, I present a brief survey of exciting developments in fast v
 ertex connectivity algorithms in the past few years that culminate in the 
 development of a celebrated 'poly-log max-flows' algorithm\, leading to an
  almost linear time vertex connectivity algorithm due to the recent breakt
 hrough in max-flow algorithms. This answers the long-standing open problem
  by Aho\, Hopcroft\, and Ullman\, and opens new research directions toward
 s computing vertex connectivity in different setting such as derandomizati
 on\, parallel algorithms\, vertex connectivity augmentation\, and many oth
 ers. \n\nhttps://math-events.uni-bonn.de/event/889/
LOCATION:Endenicher Allee 60/1-016 - Lipschitzsaal (Mathezentrum)
URL:https://math-events.uni-bonn.de/event/889/
END:VEVENT
END:VCALENDAR