- Speeding up dynamic programming.
D. Eppstein,
Z. Galil,
and
R. Giancarlo.
29th IEEE Symp. Foundations of
Comp. Sci., White Plains, New York, 1988, pp. 488–496.
Worksh. Algorithms for Molecular Genetics, Bethesda, Maryland, 1988.
Tech. Rep. CUCS-379-88, Computer Science Dept., Columbia University, 1988.
Appeared as "Efficient algorithms with applications to molecular biology" in
Int. Advanced Workshop on Sequences, Positano, Italy, 1988.
Sequences: Combinatorics, Compression, Security, Transmission,
R. M. Capocelli, ed., Springer, 1990, pp. 59–74.
The FOCS and Positano versions of this paper merged my results
on a dynamic program used for RNA secondary structure prediction,
with Raffaele's on sequence comparison.
The Bethesda talk and the TR version both used the longer title
"Speeding up dynamic programming
with application to the computation of RNA structure", and included only
the RNA result, which
used a mild convexity assumption on certain costs
to save two orders of magnitude in total time.
This work incited a boom in computational biology within the theory
community that is still going strong.
But the RNA results were quickly improved by a log factor
[Aggarwal et al. at the same FOCS] and never made it into a journal paper.
- Parallel algorithmic techniques for combinatorial computation.
D. Eppstein and
Z. Galil.
Ann. Rev. Comput. Sci. 3: 233–283, 1988.
Invited talk by Z. Galil,
16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
Springer, Lecture Notes in Comp. Sci. 372, 1989, pp. 304–318.
This survey on parallel algorithms emphasized the use of basic
subroutines such as prefix sums, Euler tours, ear decomposition, and matrix
multiplication for solving more complicated graph problems.
- Sparse dynamic programming.
D. Eppstein,
Z. Galil,
R. Giancarlo,
and G.F. Italiano.
1st ACM-SIAM Symp. Discrete Algorithms,
San Francisco, 1990, pp. 513–522.
"Sparse dynamic programming I: linear cost functions", J. ACM
39: 519–545, 1992.
"Sparse dynamic programming II: convex and concave cost functions", J. ACM 39: 546–567, 1992.
Considers sequence alignment and RNA structure problems
in which the solution is constructed by piecing together
some initial set of fragments (e.g. short sequences that match exactly).
The method is to consider a planar point set formed by
the fragment positions in the two input sequences,
and use plane sweep to construct a cellular decomposition of the plane
similar to the rectilinear Voronoi diagram.
- Efficient algorithms for sequence analysis.
D. Eppstein,
Z. Galil,
R. Giancarlo,
and G.F. Italiano.
International Advanced Workshop on
Sequences, Positano, Italy, 1991.
Sequences II: Methods in Communication, Security, and Computer Science,
R.M. Capocelli, A. De Santis, and U. Vaccaro, eds.,
Springer, 1993, pp. 225–244.
Surveys results on speeding up certain dynamic programs
used for sequence comparison and RNA structure prediction.
- Sparsification—A technique for speeding up dynamic graph algorithms.
D. Eppstein,
Z. Galil,
G.F. Italiano, and A. Nissenzweig.
33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 60–69.
Tech. Rep. RC 19272 (83907), IBM, 1993.
Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
J. ACM 44 (5): 669–696, 1997.
Uses a divide and conquer on the edge set of a graph, together with the
idea of replacing subgraphs by sparser certificates, to make various
dynamic algorithms as fast on dense graphs as they are on sparse graphs.
Applications include random generation of spanning trees
as well as finding the k
minimum weight spanning trees
for a given parameter k.
- Improved sparsification.
D. Eppstein,
Z. Galil, and
G.F. Italiano.
Tech. Rep. 93-20, ICS, UCI, 1993.
Saves a log factor over dynamic graph algorithms in
"Sparsification"
and their applications, by dividing vertices instead of edges.
Merged into the journal version of "Sparsification".
- Separator based sparsification for dynamic planar graph algorithms.
D. Eppstein,
Z. Galil,
G.F. Italiano, and T. Spencer.
25th ACM Symp. Theory of Computing, San Diego, 1993, pp. 208–217.
Replaces portions of a hierarchical separator decomposition with smaller
certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the k
best spanning trees of a planar graph.
- Separator based sparsification I:
planarity testing and minimum spanning trees.
D. Eppstein,
Z. Galil,
G.F. Italiano, and T. Spencer.
J. Comp. Sys. Sci. 52: 3–27, 1996
(special issue for 25th STOC).
First half of journal version of
Separator based sparsification for dynamic planar graph algorithms.
- Separator based sparsification II: edge and vertex connectivity.
D. Eppstein,
Z. Galil,
G.F. Italiano, and T. Spencer.
Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.
SIAM
J. Computing 28 (1): 341–381, 1999.
Second half of journal version of
Separator based sparsification for dynamic planar graph algorithms.
- Dynamic graph algorithms.
D. Eppstein,
Z. Galil,
and G.F. Italiano.
Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
Algorithms and Theoretical Computing Handbook,
M. J. Atallah, ed., CRC Press, 1999, chapter 8.
2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.