Cache-Oblivious Dynamic Programming

被引：37

作者：

Chowdhury, Rezaul Alam ^{[1
]}

Ramachandran, Vijaya ^{[1
]}

机构：

[1] Univ Texas Austin, Dept Comp Sci, Austin, TX 78712 USA

来源：

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2006年

关键词：

D O I：

10.1145/1109557.1109622

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.

引用

页码：591 / 600

页数：10

共 27 条

[1] THE INPUT OUTPUT COMPLEXITY OF SORTING AND RELATED PROBLEMS [J].

AGGARWAL, A ;

VITTER, JS .

COMMUNICATIONS OF THE ACM, 1988, 31 (09) :1116-1127

[2]

[Anonymous], P 40 ANN S FDN COMP

[3]

[Anonymous], P DAGS S PAR COMP

[4] FAST LINEAR-SPACE COMPUTATIONS OF LONGEST COMMON SUBSEQUENCES [J].

APOSTOLICO, A ;

BROWNE, S ;

GUERRA, C .

THEORETICAL COMPUTER SCIENCE, 1992, 92 (01) :3-17

[5] DYNAMIC PROGRAMMING [J].

BELLMAN, R .

SCIENCE, 1966, 153 (3731) :34-&

[6]

BLUMOFE R. D., 1996, P 8 ANN ACM S PAR AL, P297

[7]

CHERNG C, 2005, P INT C AN ALG, P49

[8]

CHOWDHURY RA, 2005, TR0543 U TEX AUST DE

[9]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[10] ALGORITHM-97 - SHORTEST PATH [J].

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345

← 1 2 3 →