2014
2015
2016
2017

The twenty-seventh meeting of the Prague computer science seminar

Monika Henzinger

Finding the global minimum cut: Flows beat PageRank

In this talk we will survey the history and the state of the art of algorithms for finding minimum cuts in graphs, including some new developments. We will focus on global minimum cuts, which is the minimum of s-t cuts over all pairs of vertices s and t.

March 23, 2017

4:00pm

Auditorium S5, MFF UK
Malostranské nám. 25, Praha 1
Show on the map

Lecture annotation

In this talk we will survey the history and the state of the art of algorithms for finding minimum cuts in graphs, including some new developments. We will focus on global minimum cuts, which is the minimum of s-t cuts over all pairs of vertices s and t. It is well-known that the value of a minimum s-t cut in a graph equals the value of the maximum flow from s to t and the standard algorithm for computing a minimum s-t cut still uses a maximum flow computation. Using that approach, however, leads to a quite inefficient algorithm for computing the global minimum cut, requiring n flow computations, where n is the number of vertices of the graph.

Indeed until recently the fastest algorithm for global minimum cut in unweighted graphs was not based on flow computation but was using multiple PageRank computations in combination with various graph-theoretic arguments. We will explain how to replace the PageRank computation by a multi-source, multi-sink flow computation that results in the fastest known algorithm for global minimum cut in unweighted graphs. This is a joint work with Satish Rao and Di Wang.

Lecturer

Monika Henzinger

Monika Henzinger is a full professor at the University of Vienna, Austria, heading the research group of Theory and Applications of Algorithms. She received her PhD in 1993 from Princeton University under the supervision of Robert Tarjan and then joined the Computer Science Department at Cornell University. Later she worked at the Systems Research Center of DEC, at Google as the Director of Research and at EPFL Lausanne, heading the Laboratory of Theory and Applications of Algorithms. In 2013 she was awarded a Dr.h.c. degree from the Technical University of Dortmund, Germany. Monika Henzinger is a fellow of the ACM and of the EATCS, she has received an ERC Advanced Grant, a European Young Investigator Award, an NSF CAREER Award, and a Top 25 Women on the Web Award. She has published over 100 scientific articles and is the co-inventor of over 80 patents.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar takes place on the 4th Thursday of each month at 4:00pm (except June, July, August and December) alternately in the buildings of Faculty of Electrical Engineering, Czech Technical University, Karlovo nám. 13, Praha 2 and Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, Praha 1.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures is in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Michal Chytil (Czech Academy of Sciences, Computer Science Institute), Pavel Kordík (Czech Tech. Univ., Faculty of Information Technologies), Jan Kybic (Czech Tech. Univ., Faculty of Electrical Engineering), Michal Pěchouček (Czech Tech. Univ., Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (Czech Tech. Univ., Faculty of Electrical Engineering), and Filip Železný (Czech Tech. Univ., Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact