BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250328T120000
DTEND;TZID=Asia/Kolkata:20250328T170000
DTSTAMP:20260924T055342
CREATED:20250327T132705Z
LAST-MODIFIED:20250327T132705Z
UID:1468-1743163200-1743181200@homecse.iitd.ac.in
SUMMARY:An amazing structure for representing all Steiner mincuts of a graph
DESCRIPTION:Speaker: Surender Baswana\, IIT Kanpur \n  \nAbstract: \nMincuts are one of the most well-researched topics in algorithms. In recent years\, there has been phenomenal research on algorithms for computing (s\, t)-mincuts and global mincuts. On the other hand\, the data structural and graph theoretical aspects of mincuts have also been well-researched in the last 50 years\, though they are not as widely known despite being very fundamental and seminal. \n\nWe shall begin with a light discussion of the following 2 classical results. (1) There is a directed acyclic graph that stores all (s\,t)-mincuts of a graph. (2) There is a tree-like graph that stores all global mincuts of a graph.  We shall then discuss a structure that stores Steiner mincuts – generalization of (s\,t)-mincuts and global mincuts. This structure\, designed by Dinitz and Vainshtein is amazingly elegant and beautiful. We shall discuss this structure along with new and much simpler proofs of its properties. \n\nNote: Anyone with basic knowledge of algorithms and elementary graph theory should be able to follow most of the talk. \n\nBiography of the Speaker: \nSurender Baswana is the Tapas Misra Memorial Chair Professor at the Department of Computer Science and Engineering at IIT Kanpur. He did BTech\, MTech\, and PhD from IIT Delhi\, and was a postdoctoral researcher at the Max Planck Institute for Computer Science. He has been a faculty member at IIT Kanpur since 2006. His research area is the design and analysis of algorithms.
URL:https://homecse.iitd.ac.in/event/an-amazing-structure-for-representing-all-steiner-mincuts-of-a-graph/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR