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
- Computer Science Department Graduate Admissions Committee
Professional Activities
- Referee: Journal of the ACM; 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; 27th Annual ACM Symposium on
Theory of Computing; Lecture Notes in Computer Science, Springer-Verlag
- Consultant, NEC Research Institute
- Visiting Scientist at the International Computer Science Institute,
Berkeley, California
Award
- NSF Faculty Early Career Development Award (1995-1998)
Lectures
- Incremental algorithms for approximate minimum cuts in a multigraph.
International Computer Science Institute, Berkeley, California,
August 1994.
- Dynamic graph algorithms in polylogarithmic time per operation.
Columbia Theory Day, Columbia University, New York, New York,
April 1995.
- ___. University of California at Berkeley, Berkeley, California, May 1995.
- ___. Stanford University, Stanford, California, May 1995.
- ___. AT&T Bell Laboratory, Murray Hill, New Jersey, June 1995.
Publications
- Fully dynamic cycle-equivalence in graphs. Proceedings of the 35th
Annual IEEE Symposium on Foundations of Computer Science
(November 1994), 744-755.
- Average case analysis of dynamic graph algorithms. Proceedings of
the 6th Annual ACM-SIAM Symposium on Discrete Algorithms
(January 1995), 312-321 (with David Alberts).
- Randomized dynamic graph algorithms with polylogarithmic time per
operation. Proceedings of the 27th Annual ACM Symposium on Theory
of Computing (June 1995), 519-527 (with Valerie King).
- Approximating minimum cuts under insertions. Proceedings of the 22nd
International Colloquium on Automata, Languages and Programming
(July 1995), LNCS 944, 280-291.
- Fully dynamic bi-connectivity in graphs. Algorithmica 13 (1995), 503-538.
Return to:
1994-1995 Annual Report Home Page
-
Departmental Home Page
If you have questions or comments please contact:
www@cs.cornell.edu.
Last modified: 24 November 1995 by Denise Moore
(denise@cs.cornell.edu).