Joint ICE-TCS@Reykjavik University/GSSI virtual seminar — speaker: Monika Henzinger

Speaker: Monika Henzinger (University of Vienna, Austria)
WWW: https://homepage.univie.ac.at/monika.henzinger/

Title: Hierarchical graph decompositions in dynamic algorithms.

Abstract: A dynamic graph algorithm is a data structure that maintains a graph property while the graph undergoes a sequence of edge updates.  In dynamic graph algorithms with polylogarithmic time per operation a hierarchical graph decomposition is typically maintained. We present various such hierarchies and the different types of invariants used to maintain them efficiently. They lead to fast dynamic algorithms for connectivity, approximate matching, vertex cover, densest subgraph and set cover as well as for (Delta+1)-vertex coloring.
Biographical sketch:

Monika Henzinger is 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 and was an assistant professor at Cornell University, a researcher at Digital Equipment Corporation, the Director of Research at Google and a professor at EPFL, Switzerland, before moving to the University of Vienna.

Professor Henzinger received a Dr. h. c. degree from the Technical University of Dortmund, Germany, an ERC Advanced Grant, a SIGIR Test of Time Award, a European Young Investigator Award, an NSF CAREER Award, and a Top 25 Women on the Web Award. She is a fellow of the ACM and of the EATCS and a member of the Austrian Academy of Sciences and the German Academy of Sciences Leopoldina and has served as the ACM Symposium on the Theory of Computing (STOC 2018) program committee chair.

She is also a member of the supervisory board of AMS AG and of the Swiss and Austrian Science Board. Her scientific work consists of over 170 scientific articles and over 80 patents.