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

This data set contains WWW-pages collected from computer science departments of various universities

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

<title>Monika Rauch Henzinger: Publications</title>
<h2>List of Publications</h2>
<i><a href="http://www.cs.cornell.edu/Info/People/mhr/home.html">
Monika Rauch Henzinger</a></i>
<h3><a name="data_structures">Data Structures</a></h3><OL>

<P><LI> Monika H. Rauch.
<b>Fully Dynamic Biconnectivity in Graphs.</b>
In 
<i>Algorithmica</i>, 13:503-538, 1995.
A preliminary version appeared in the 
<i>Proceedings of the 
33rd Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1992), pp. 50-59.
<a href ="abstract/ab1.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/2-vertex-paper1.ps">
postscript.</a>

<p>
<li>John Hershberger, Monika Rauch, and Subhash Suri.
<b>Fully Dynamic 
Two-Edge-Connectivity in Planar Graphs.</b>
<i>Theoretical Computer Science,</i> Special Issue on
Dynamic and On-line Algorithms, 130:139-161, 1994.
<a href="abstract/ab2.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/2-edge.ps">
postscript.</a>
<p>
<li>Pino Italiano, Han La Poutre, and Monika Rauch.
<b>Fully Dynamic 
Planarity Testing in Embedded Graphs.</b>
<i>Proceedings of the 
First Annual European Symposium on Algorithms</i>
(ESA 1993), pp. 212-223.
<a href="abstract/ab3.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/planarity-testing.ps">
postscript.</a>
<p>
<li>Monika H. Rauch.
<b>Improved Data Structures for Fully Dynamic Biconnectivity.</b>
<i>Proceedings of the 
26th Annual ACM Symposium on Theory of Computing</i>
(STOC 1994), pp. 686-695.
<a href="abstract/ab4.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/2-vertex-paper2.ps">
postscript.</a>
<p>
<li>Monika Rauch 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 Rauch 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 Rauch 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 Rauch 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 Rauch 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 Rauch Henzinger and Valerie King.
<b>Fully Dynamic Biconnectivity and Transitive Closure.</b>
<i>Proceedings of the 
36th Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1995), pp. 664-672.
<a href="abstract/ab10.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/transitive.ps">
postscript.</a>

<h3><a name="Randomized Algorithms">Randomized Algorithms</a></h3>
<p>
<li>Monika Rauch 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, pp. 290-299.
<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 Algorithms">Graph Algorithms</a></h3>
<p>
<li>Brandon Dixon, Monika Rauch, and Robert E. Tarjan.
<b>Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.</b>
<i>SIAM Journal on Computing</i> 21(6):1184-1192, 1992.
<a href="abstract/ab11.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/verification.ps">
postscript.</a>
<p>
<li>Philip Klein, Satish Rao, Monika Rauch, Sairam Subramanian.
<b>Faster Shortest-Path Algorithms for Planar Graphs.</b>
<i>Proceedings of the 
26th Annual ACM Symposium on Theory of Computing</i>
(STOC 1994), pp. 27-37. Invited to a special issue of 
<i>Journal of Computer and System Sciences</i> on selected papers of
STOC 1994.
<a href="http://www.cs.cornell.edu/Info/People/mhr/abstract/ab12.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/shortest-path.ps">
postscript.</a>
<p>
<li>Monika R. Henzinger, Thomas A. Henzinger, and Peter Kopke.
<b>Computing Simulations in Finite and Infinite Graphs.</b>
<i>Proceedings of the 
36th Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1995), pp. 453-462.
<a href="abstract/ab13.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/simulations.ps">
postscript.</a>
<p>
<p>
<li>Monika Rauch 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), pp. 333-340.
<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).
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/swat96.ps">
postscript.</a>
<p>
<li>Monika R. Henzinger, Satish Rao, and Hal N. Gabow.
<b>Computing Vertex Connectivity: New Bounds from Old Techniques.</b>
<i>Proceedings of the 
37th Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1996).
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/focs96.ps">
postscript.</a>

<h3><a name="Graph Theory">Graph Theory</a></h3>
<p>
<li>Monika Rauch Henzinger and David Williamson.
<b>On the Number of Small Cuts in a Graph.</b>
<i>Information Processing Letters</i> 59, 1996, pp. 41-44.
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/small.ps">
postscript.</a>
<h3><a name="Lower Bounds">Lower Bounds</a></h3>
<p>
<li>Kurt Mehlhorn, Stefan Naher, and Monika Rauch.
<b>The Complexity of a Game related to the Dictionary Problem.</b>
<i>SIAM Journal on Computing</i> 19(5):902-906, 1990.
A preliminary version appeared in the 
<i>Proceedings of the 
30rd Annual IEEE Symposium on Foundations of Computer Science</i>
(FOCS 1989), pp. 546-548.
<a href="abstract/ab14.gif">
Abstract.</a>
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/lower1.html">
gif.</a>
<p>
<li>Michael L. Fredman and Monika Rauch Henzinger.
<b>Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.</b>
<a href="abstract/ab15.gif">
Abstract.</a>
<i>Algorithmica</i> to appear.
Ftp
<a href="http://www.cs.cornell.edu/Info/People/mhr/papers/lower2.ps">
postscript.</a>
</ol>

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