Monika Rauch Henzinger
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
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
- NSF Faculty Early Career Development Award
- Visiting Scientist: International Computer Science Institute,
- Program Committee Member: 28th Annual ACM Symposium on Theory of
Computing, 1996; 8th Annual ACM-SIAM Symposium on Discrete Algorithms
- Guest Editor: Journal of Computer and Systems Sciences,
Special Issue on Selected Paper of STOC 96
- Referee: SIAM Journal on Computing; Journal of Computer
and Systems Sciences; Journal of Algorithms;
Algorithmica; Theoretical Computer Science; 35th Annual
IEEE Symposium on Foundations of Computer Science, 6th Annual ACM-SIAM
Symposium on Discrete Algorithms
- Consultant: NEC Research Institute
- Dynamic algorithms-a survey. Computer Science Department,
Friedrich-Alexander University, Erlangen, Germany, July 1996.
- Monoton sparsification and dynamic algorithms for reachability
problems in directed graphs. Computer Science, Cornell University,
Ithaca, NY, November 1995.
- Dynamic graph algorithms in polylogarithmic time. AT&T Bell
Laboratories, Murray Hill, NJ, July 1995.
- Improved sampling with applications to dynamic graph algorithms.
Proceedings of the 23rd International Colloquium on Automata,
Languages, and Programming, Springer-Verlag, July 1996, 290-299 (with
- Faster algorithms for the nonemptiness of Streett automata and for
communication protocol pruning. Proceedings of the 5th Scandinavian
Workshop on Algorithm Theory (SWAT'96), June 1996,10-20 (with Jan
- Constructing a tree from homeomorphic subtrees. Proceedings of the
7th Annual Symposium on Discrete Algorithms, January 1996, 333-340
(with Valerie King and Tandy Warnow).
- Fully dynamic biconnectivity and transitive closure. Proceedings of
the Annual Symposium on Foundations of Computer Science, October 1995,
664-672 (with Valerie King).
- Computing simulations in finite and infinite graphs. Proceedings of
the 36th Annual Symposium on Foundations of Computer Science, October
1995, 453-462 (with Thomas A. Henzinger, and Peter W. Kopke).
- Certificates and fast algorithms for biconnectivity in fully-dynamic
graphs. Proceedings of the Third Annual European Symposium on
Algorithms ESA'95, September 1995, 171-184 (with Han La Poutré).
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