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

Data Structures

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

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

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

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

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

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

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

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

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

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

    Randomized Algorithms

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

    Graph Algorithms

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

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

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

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

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

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

    Graph Theory

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

    Lower Bounds

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

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