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
- 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:
- 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 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.
- 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.
- 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:
-
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 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.
- 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.
- 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.
- 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.
- 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.
- Michael L. Fredman and Monika R. Henzinger.
Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.
to appear in Algorithmica
Abstract.
Ftp
postscript.
- 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