Monika Rauch Henzinger
Assistant Professor
mhr@cs.cornell.edu
http://www.cs.cornell.edu/home/mhr/mhr.html
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
lineartime 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 lineartime
algorithm for computing the shortest paths in a planar graph from a
given source node to all other nodes. Recently, I gave the first
preflowpush algorithm for computing the vertex connectivity of a
graph.
Awards
 NSF Faculty Early Career Development Award
University Activities
 Visiting Scientist: International Computer Science Institute,
Berkeley, CA.
Professional Activities
 Program Committee Member: 28th Annual ACM Symposium on Theory of
Computing, 1996; 8th Annual ACMSIAM 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 ACMSIAM
Symposium on Discrete Algorithms
 Consultant: NEC Research Institute
Lectures
 Dynamic algorithmsa survey. Computer Science Department,
FriedrichAlexander 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.
Publications
 Improved sampling with applications to dynamic graph algorithms.
Proceedings of the 23rd International Colloquium on Automata,
Languages, and Programming, SpringerVerlag, July 1996, 290299 (with
Mikkel Thorup).
 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,1020 (with Jan
Arne Telle).
 Constructing a tree from homeomorphic subtrees. Proceedings of the
7th Annual Symposium on Discrete Algorithms, January 1996, 333340
(with Valerie King and Tandy Warnow).
 Fully dynamic biconnectivity and transitive closure. Proceedings of
the Annual Symposium on Foundations of Computer Science, October 1995,
664672 (with Valerie King).
 Computing simulations in finite and infinite graphs. Proceedings of
the 36th Annual Symposium on Foundations of Computer Science, October
1995, 453462 (with Thomas A. Henzinger, and Peter W. Kopke).
 Certificates and fast algorithms for biconnectivity in fullydynamic
graphs. Proceedings of the Third Annual European Symposium on
Algorithms ESA'95, September 1995, 171184 (with Han La Poutré).
Return to:

19951996 Annual Report Home Page

Departmental Home Page
If you have questions or comments please contact:
www@cs.cornell.edu.
Last modified: 2 November 1996 by Denise Moore
(denise@cs.cornell.edu).