All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
From MaRDI portal
Publication:4210080
DOI10.1137/S0097539795288489zbMath0907.68076MaRDI QIDQ4210080
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items
Algorithms For Computing Approximate Repetitions In Musical Sequences, A substring-substring LCS data structure, A survey of the all-pairs shortest paths problem and its variants in graphs, Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions, Efficient algorithms for finding interleaving relationship between sequences, Two algorithms for LCS consecutive suffix alignment, Longest common subsequence problem for unoriented and cyclic strings, A dynamic edit distance table, Linear-space S-table algorithms for the longest common subsequence problem, Unified compression-based acceleration of edit-distance computation, A fully compressed algorithm for computing the edit distance of run-length encoded strings, Monge properties of sequence alignment, Sequence Alignment Algorithms for Run-Length-Encoded Strings, An almost quadratic time algorithm for sparse spliced alignment, Mining approximate patterns with frequent locally optimal occurrences, Unnamed Item, Periodicity algorithms and a conjecture on overlaps in partial words, Efficient all path score computations on grid graphs, Linear time algorithm for the longest common repeat problem, Dynamic edit distance table under a general weighted cost function, ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS, On almost Monge all scores matrices, On the advice complexity of the online dominating set problem, An all-substrings common subsequence algorithm, Tandem cyclic alignment, New complexity results for the \(k\)-covers problem, Shortest-path queries in static networks, Combinatorics on partial word correlations, Approximate periods of strings, Semi-local longest common subsequences in subquadratic time, Approximate labelled subtree homeomorphism, Periodic String Comparison, Sparse LCS common substring alignment, Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time, Unnamed Item, Unnamed Item, Repetitive perhaps, but certainly not boring, Unnamed Item, Approximate periodicity, Implementing approximate regularities, Discovering instances of poetic allusion from anthologies of classical Japanese poems
