David Eppstein

*J. Algorithms* 11(1):85–101, Mar 1990

Tech. report CUCS-382-88, Columbia Univ., Computer Science Dept., 1988

*Mathematical Reviews* 91h:68031

Cited by:

- Improved algorithms for economic lot size problems
- Selection in monotone matrices and computing $k$th nearest neighbors
- Image analysis and computer vision: 1990
- On-line dynamic programming with applications to the prediction of RNA secondary structure
- Dynamic programming with convexity, concavity and sparsity
- Selection and sorting in totally monotone arrays
- Improved selection in totally monotone arrays
- Linear and $O(n\log n)$ time minimum-cost matching algorithms for quasi-convex tours
- A linear time algorithm for concave one-dimensional dynamic programming
- Finding least-weight subsequences with fewer processors
- Parallel algorithms for dynamic programming recurrences with more than $O(1)$ dependency
- Superlinear bounds for matrix searching problems
- A special case of the $n$-vertex traveling-salesman problem that can be solved in $O(n)$ time
- Dynamic programming: special cases
- Approximate regular expression pattern matching with concave gap penalties
- Efficient algorithms for some path partitioning problems
- Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
- Perspectives of Monge properties in optimization
- Fast solution and detection of minimal forecast horizons in dynamic programs with a single indicator of the future – applications to dynamic lot-sizing models
- Parallel dynamic programming
- Discrete Pattern Matching over Sequences and Interval Sets
- Shortest path in complete bipartite digraph problem and its applications
- Efficiently solvable special cases of hard combinatorial optimization problems
- Structured $p$-facility location problems on the line solvable in polynomial time
- Well-solvable special cases of the traveling salesman problem: A survey
- Process Discovery and Validation through Event-Data Analysis
- Software process validation: quantitatively measuring the correspondence of a process to a model using event-based data
- An algorithm for shortest paths in bipartite digraphs with concave weight matrices and its applications
- Monge strikes again: optimal placement of web proxies in the Internet
- Approximation of staircases by staircases
- A sub-quadratic sequence alignment algorithm for unrestricted cost matrices
- A faster off-line algorithm for the TCP acknowledgement problem
- Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics
- Sparse LCS common substring alignment
- Note on approximate comparison of sequences with normalization