Monika Rauch Henzinger
Assistant Professor
Ph.D. Princeton University, 1993

My area of research is the design and analysis of algorithms and data structures in general and dynamic graph algorithms in particular. Dynamic graph algorithms are algorithms that maintain a certain property of a changing graph more efficiently than algorithms that recompute the property from scratch after every change. In a recent breakthrough, I gave the first dynamic algorithm that maintains connected components and various other properties of a graph in polylogarithmic time per graph modification.

Dynamic algorithms maintain essential information during the first execution of a program to speed up subsequent executions on similar inputs. I applied dynamic graph algorithms to problems arising in various fields of computer science. For example, I developed an almost linear-time algorithm for the consensus tree problem, which arises in data bases and computational biology. I also gave a faster algorithm for testing the emptiness of Streett Automata and for communication protocol pruning.

Another focus of my research is the design of efficient algorithms for optimization problems. For example, I developed the first linear-time algorithm for computing the shortest paths in a planar graph from a given source node to all other nodes. Recently, I gave the first preflow-push algorithm for computing the vertex connectivity of a graph.


University Activities

Professional Activities



Return to:
1995-1996 Annual Report Home Page
Departmental Home Page

If you have questions or comments please contact:

Last modified: 2 November 1996 by Denise Moore (