David Eppstein - Publications

• 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.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.