MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:21:30 GMT
Content-Type: text/html
Content-Length: 8862
Last-Modified: Sunday, 06-Oct-96 22:59:14 GMT
Monika Rauch Henzinger: Publications
List of Publications
Monika Rauch Henzinger
- Monika H. Rauch.
Fully Dynamic Biconnectivity in Graphs.
In
Algorithmica, 13:503-538, 1995.
A preliminary version appeared in the
Proceedings of the
33rd Annual IEEE Symposium on Foundations of Computer Science
(FOCS 1992), pp. 50-59.
Abstract.
Ftp
postscript.
- John Hershberger, Monika Rauch, and Subhash Suri.
Fully Dynamic
Two-Edge-Connectivity in Planar Graphs.
Theoretical Computer Science, Special Issue on
Dynamic and On-line Algorithms, 130:139-161, 1994.
Abstract.
Ftp
postscript.
- Pino Italiano, Han La Poutre, and Monika Rauch.
Fully Dynamic
Planarity Testing in Embedded Graphs.
Proceedings of the
First Annual European Symposium on Algorithms
(ESA 1993), pp. 212-223.
Abstract.
Ftp
postscript.
- Monika H. Rauch.
Improved Data Structures for Fully Dynamic Biconnectivity.
Proceedings of the
26th Annual ACM Symposium on Theory of Computing
(STOC 1994), pp. 686-695.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger.
Fully Dynamic Cycle-Equivalence in Graphs.
Proceedings of the
35rd Annual IEEE Symposium on Foundations of Computer Science
(FOCS 1994), pp. 744-755.
Abstract.
Ftp
postscript.
For applications of cycle-equivalence in compilers see:
- Richard Johnson, David Pearson, and Keshav Pingali.
Finding Regions Fast: Single Entry Single Exit and Control Regions
in Linear Time.
Proceedings of ACM SIGPLAN '94 Conference on Programming Language Design and
Implementation, pp. 171-185.
- Robert E. Tarjan and Jacobo Valdes.
Prime subprogram parsing of a program.
Conference Record of the seventh Annual ACM Symposium on Principles
of Programming Languages (POPL 1980), pp. 28-30.
- David Alberts and Monika Rauch Henzinger.
Average Case Analysis of Dynamic Graph Algorithms.
Proceedings of the
Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA 1995), pp. 312-321.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger.
Approximating Minimum Cuts under Insertions.
Proceedings of the
22nd International Colloquium on Automata, Languages, and Programming
(ICALP 1995), Lecture Notes in Computer Science 944,
Springer-Verlag, 1995, pp. 280-291.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger and Valerie King.
Randomized Dynamic Graph Algorithms with Polylogarithmic Time
per Operation.
Proceedings of the
27th Annual ACM Symposium on Theory of Computing
(STOC 1995), pp. 519-527. Invited to a special issue of
Journal of Computer and System Sciences on selected papers of
STOC 1995.
Abstract.
Ftp
postscript.
Implementation by David Alberts:
-
Source Code
- David Alberts, Giuseppe Cattaneo, and Giuseppe F. Italiano.
An Empirical Study of Dynamic Graph Algorithms.
Proceedings of the
Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA 1996).
- Monika Rauch Henzinger and Han La Poutre.
Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic
Graphs.
Proceedings of the
Third Annual European Symposium on Algorithms
(ESA 1995), pp. 171-184.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger and Valerie King.
Fully Dynamic Biconnectivity and Transitive Closure.
Proceedings of the
36th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 1995), pp. 664-672.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger and Mikkel Thorup.
Improved Sampling with Applications to Dynamic Graph Algorithms.
Proceedings of the
23rd International Colloquium on Automata, Languages, and Programming
(ICALP 1996), Lecture Notes in Computer Science,
Springer-Verlag, 1996, pp. 290-299.
Abstract.
Ftp
postscript.
- Brandon Dixon, Monika Rauch, and Robert E. Tarjan.
Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.
SIAM Journal on Computing 21(6):1184-1192, 1992.
Abstract.
Ftp
postscript.
- Philip Klein, Satish Rao, Monika Rauch, Sairam Subramanian.
Faster Shortest-Path Algorithms for Planar Graphs.
Proceedings of the
26th Annual ACM Symposium on Theory of Computing
(STOC 1994), pp. 27-37. Invited to a special issue of
Journal of Computer and System Sciences on selected papers of
STOC 1994.
Abstract.
Ftp
postscript.
- Monika R. Henzinger, Thomas A. Henzinger, and Peter Kopke.
Computing Simulations in Finite and Infinite Graphs.
Proceedings of the
36th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 1995), pp. 453-462.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger, Valerie King, and Tandy Warnow.
Constructing a Tree from Homeomorphic Subtrees.
Proceedings of the 7th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA 1996), pp. 333-340.
Abstract.
Ftp
postscript.
- Monika Rauch Henzinger and Jan Arne Telle.
Faster Algorithms for the Nonemptiness of Streett Automata and
for Communication Protocol Pruning.
Proceedings of the 5th
Scandinavian Workshop on Algorithm Theory(SWAT'96).
Ftp
postscript.
- Monika R. Henzinger, Satish Rao, and Hal N. Gabow.
Computing Vertex Connectivity: New Bounds from Old Techniques.
Proceedings of the
37th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 1996).
Ftp
postscript.
- Monika Rauch Henzinger and David Williamson.
On the Number of Small Cuts in a Graph.
Information Processing Letters 59, 1996, pp. 41-44.
Ftp
postscript.
- Kurt Mehlhorn, Stefan Naher, and Monika Rauch.
The Complexity of a Game related to the Dictionary Problem.
SIAM Journal on Computing 19(5):902-906, 1990.
A preliminary version appeared in the
Proceedings of the
30rd Annual IEEE Symposium on Foundations of Computer Science
(FOCS 1989), pp. 546-548.
Abstract.
Ftp
gif.
- Michael L. Fredman and Monika Rauch Henzinger.
Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.
Abstract.
Algorithmica to appear.
Ftp
postscript.
Last updated on September 18, 1996.
mhr@cs.cornell.edu