Monika Rauch Henzinger

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 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.

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 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

Lectures

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.

Publications

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 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,10-20 (with Jan Arne Telle).
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é).

Return to:

1995-1996 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).