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.
(Bibtex: Positano, FOCS -- Citations -- Citations of "Efficient algorithms..." -- MIT hypertext bibliography -- CiteSeer)
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.
(BibTeX -- Citations -- CiteSeer -- ACM DL (ARCS) -- ACM DL (ICALP))
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.
(BibTeX -- Citations to conference version -- Citations to SDP I -- Citations to SDP II)
Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
(BibTeX -- Citations -- CiteSeer)
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.
(BibTeX -- Citations -- MIT hypertext bibliography -- ACM DL)
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".
(BibTeX -- Citations -- CiteSeer)
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.
(BibTeX -- Citations -- MIT hypertext bibliography)
First half of journal version of Separator based sparsification for dynamic planar graph algorithms.
Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.
(BibTeX -- Citations -- CiteSeer)
Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.