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 NPhard 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 lineartime
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 ACMSIAM
Symposium on Discrete Algorithms; 27th Annual ACM Symposium on
Theory of Computing; Lecture Notes in Computer Science, SpringerVerlag
 Consultant, NEC Research Institute
 Visiting Scientist at the International Computer Science Institute,
Berkeley, California
Award
 NSF Faculty Early Career Development Award (19951998)
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 cycleequivalence in graphs. Proceedings of the 35th
Annual IEEE Symposium on Foundations of Computer Science
(November 1994), 744755.
 Average case analysis of dynamic graph algorithms. Proceedings of
the 6th Annual ACMSIAM Symposium on Discrete Algorithms
(January 1995), 312321 (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), 519527 (with Valerie King).
 Approximating minimum cuts under insertions. Proceedings of the 22nd
International Colloquium on Automata, Languages and Programming
(July 1995), LNCS 944, 280291.
 Fully dynamic biconnectivity in graphs. Algorithmica 13 (1995), 503538.
Return to:

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