Abstract: Mincuts 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.
We 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.

Note: Any one with basic knowledge of algorithms and elementary graph theory should be able to follow most of the seminar.

About the Speaker: Surender 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 Delhi since 2006. His research area is the design and analysis of algorithms.

We look forward to your active participation.