http:^^www.cs.cornell.edu^info^people^mhr^project.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 162 行

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

<title>Dynamic Graph Algorithms Monika Henzinger Monika Rauch Dynamic Graph Algorithm</title>
<h2>Design and Analysis of Efficient Dynamic Graph Algorithms</h2>
<i><a href="http://www.cs.cornell.edu/Info/People/mhr/home.html">
Monika R. Henzinger</a></i>

<h3><a name="data_structures">Dynamic Graph Algorithms</a></h3><OL>

<p>
<li>Monika R. Henzinger.
<b>Fully Dynamic Cycle-Equivalence in Graphs.</b>
<i>Proceedings of the 
35rd Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1994), pp. 744-755.
<a href="abstract/ab5.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/cycle-equiv.ps">
postscript.</a>
<p>For applications of cycle-equivalence in compilers see:
<ul>
<li>Richard Johnson, David Pearson, and Keshav Pingali.
<b>Finding Regions Fast: Single Entry Single Exit and Control Regions
in Linear Time.</b> 
<i>Proceedings of ACM SIGPLAN '94 Conference on Programming Language Design and
   Implementation,</i> pp. 171-185.
<li>Robert E. Tarjan and Jacobo Valdes.
<b>Prime subprogram parsing of a program.</b>
<i>Conference Record of the seventh Annual ACM Symposium on Principles
of Programming Languages</i> (POPL 1980), pp. 28-30.
</ul>
<p>
<li>David Alberts and Monika R. Henzinger.
<b>Average Case Analysis of Dynamic Graph Algorithms.</b>
<i>Proceedings of the 
Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>
(SODA 1995), pp. 312-321.
<a href="abstract/ab6.gif">Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/average.ps">
postscript.</a>
<p>
<li>Monika R. Henzinger.
<b>Approximating Minimum Cuts under Insertions.</b>
<i>Proceedings of the 
22nd International Colloquium on Automata, Languages, and Programming</i>
(ICALP 1995), Lecture Notes in Computer Science 944,
Springer-Verlag, 1995, pp. 280-291.
<a href="abstract/ab7.gif">Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/mincut.ps">
postscript.</a>
<p>
<li>Monika R. Henzinger and Valerie King.
<b>Randomized Dynamic Graph Algorithms with Polylogarithmic Time
per Operation.</b>
<i>Proceedings of the 
27th Annual ACM Symposium on Theory of Computing</i>
(STOC 1995), pp. 519-527. Invited to a special issue of 
<i>Journal of Computer and System Sciences</i> on selected papers of
STOC 1995.
<a href="abstract/ab8.gif">Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/connectivity.ps">
postscript.</a>
<p>
Implementation by David Alberts:
<ul>
<li><a href="ftp://ftp.inf.fu-berlin.de/pub/misc/dyn_con">
Source Code</a>
<li>David Alberts, Giuseppe Cattaneo, and Giuseppe F. Italiano.
<b>An Empirical Study of Dynamic Graph Algorithms.</b>
<i>Proceedings  of the 
Seventh Annual ACM-SIAM Symposium on Discrete Algorithms</i>
(SODA 1996).
</ul>
<p>
<li>Monika R. Henzinger and Han La Poutre.
<b>Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic 
Graphs.</b>
<i>Proceedings of the 
Third Annual European Symposium on Algorithms</i>
(ESA 1995), pp. 171-184.
<a href="abstract/ab9.html">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/certificates.ps">
postscript.</a>
<p>
<li>Monika R. Henzinger and Valerie King.
<b>Fully Dynamic Biconnectivity and Transitive Closure.</b>
To appear in
<i>Proceedings of the 
36th Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1995).
<a href="abstract/ab10.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/transitive.ps">
postscript.</a>

<p>
<li>Monika R. Henzinger and Mikkel Thorup.
<b>Improved Sampling with Applications to Dynamic Graph Algorithms.</b>
<i>Proceedings of the 
23rd International Colloquium on Automata, Languages, and Programming</i>
(ICALP 1996), Lecture Notes in Computer Science,
Springer-Verlag, 1996.
<a href="abstract/ab106.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/sampling.ps">
postscript.</a>

<h3><a name="Graph Theory">Applications of dynamic graph algorithms</a></h3>
<p>
<li>Monika R. Henzinger, Valerie King, and Tandy Warnow.
<b>Constructing a Tree from Homeomorphic Subtrees.</b>
<i>Proceedings of the 7th Annual ACM-SIAM Symposium
on Discrete Algorithms</i> (SODA 1996).
<a href="abstract/ab105.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/bio.ps">
postscript.</a>
<p>
<li>Monika Rauch Henzinger and Jan Arne Telle.
<b>Faster Algorithms for the Nonemptiness of Streett Automata and
for Communication Protocol Pruning.</b>
<i>Proceedings of the 5th
Scandinavian Workshop on Algorithm Theory</i>(SWAT'96).
<a href="abstract/miss.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/swat96.html">
postscript.</a>

<h3><a name="Lower Bounds">Lower bounds for dynamic graph algorithms</a></h3>
<p>
<li>Michael L. Fredman and Monika R. Henzinger.
<b>Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.</b>
<i>to appear in Algorithmica</i>
<a href="abstract/ab15.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/lower2.ps">
postscript.</a>
<p>
<li>P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia.
<b>Complexity Models for Incremental Computation.</b>
<i> Theoret. Comput. Science 130, 1994, 203--236.</i>
</ol>

<i>Last updated on June 18, 1996.<br>
[e-mail]</i>