Monika Rauch Henzinger
Assistant Professor
PhD 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. I am using these new results to improve the running time of approximation algorithms for NP-hard optimization problems, such as the traveling salesman problem.

Another key direction of my research is the design of efficient algorithms for optimization problems. Recently, 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. I also showed a new upper bound on the number of "small" cuts in a graph. My next goal is to develop faster deterministic approximation algorithms for various minimum cut and maximum flow problems.

University Activities

Professional Activities




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

If you have questions or comments please contact:

Last modified: 24 November 1995 by Denise Moore (