MIME-Version: 1.0 Server: CERN/3.0 Date: Sunday, 24-Nov-96 22:21:25 GMT Content-Type: text/html Content-Length: 5321 Last-Modified: Friday, 22-Nov-96 04:31:42 GMT Dynamic Graph Algorithms Monika Henzinger Monika Rauch Dynamic Graph Algorithm

Design and Analysis of Efficient Dynamic Graph Algorithms

Monika R. Henzinger

Dynamic Graph Algorithms

  1. Monika R. 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:

  2. David Alberts and Monika R. 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.

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

  4. Monika R. 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:

  5. Monika R. 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.

  6. Monika R. Henzinger and Valerie King. Fully Dynamic Biconnectivity and Transitive Closure. To appear in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1995). Abstract. Ftp postscript.

  7. Monika R. 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. Abstract. Ftp postscript.

    Applications of dynamic graph algorithms

  8. Monika R. 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). Abstract. Ftp postscript.

  9. 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). Abstract. Ftp postscript.

    Lower bounds for dynamic graph algorithms

  10. Michael L. Fredman and Monika R. Henzinger. Lower Bounds for Fully Dynamic Connectivity Problems in Graphs. to appear in Algorithmica Abstract. Ftp postscript.

  11. P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia. Complexity Models for Incremental Computation. Theoret. Comput. Science 130, 1994, 203--236.
Last updated on June 18, 1996.
mhr@cs.cornell.edu