CTU Events

27. PIS Prof. Monika Henzinger: Finding the global minimum cut: Flows beat PageRank

23 Mar 2017   16:00

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 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 will take 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 will consist of a one-hour lecture followed by a discussion. The lecture should be 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 will be in English.
The seminar framework was laid out by the preparatory committee consisting of 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), 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.

Place

S5, MFF UK, Malostranské nám. 25, Praha 1

Organizer

Přípravný výbor PIS

Contact person

Veronika Šínová, info@praguecomputerscience.cz, 224357667

More information

http://praguecomputerscience.cz/index.php?l=en&p=27