David Eppstein - Publications

• Finding the k shortest paths.
  D. Eppstein.
  35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154-165.
  Tech. Rep. 94-26, ICS, UCI, 1994.
  SIAM J. Computing 28(2):652-673, 1998.

  Finds multiple short paths connecting two terminals in a graph (allowing repeated vertices and edges in the paths) in constant time per path after a preprocessing stage dominated by a single-source shortest path computation. Applications include dynamic programs for the knapsack problem, biological sequence alignment, and maximum inscribed polygons.

  (BibTeX -- Full paper -- Citations -- Graehl implementation -- Jiménez-Marzal implementations -- Shibuya implementation -- Martins implementation -- CiteSeer: TR '94, SJC '98 -- ACM DL)

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

Semi-automatically filtered from a common source file.