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/S0097539795288489zbMATH Open0907.68076MaRDI QIDQ4210080FDOQ4210080
Authors: Jeanette P. Schmidt 
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Cited In (43)
- Tandem cyclic alignment
- New complexity results for the \(k\)-covers problem
- A survey of the all-pairs shortest paths problem and its variants in graphs
- On the advice complexity of the online dominating set problem
- Discovering instances of poetic allusion from anthologies of classical Japanese poems
- A substring-substring LCS data structure
- A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
- Monge properties of sequence alignment
- An almost quadratic time algorithm for sparse spliced alignment
- Linear time algorithm for the longest common repeat problem
- ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
- Semi-local longest common subsequences in subquadratic time
- Algorithms For Computing Approximate Repetitions In Musical Sequences
- Linear-space S-table algorithms for the longest common subsequence problem
- On almost Monge all scores matrices
- Sparse LCS common substring alignment
- Exact distance oracles for planar graphs
- Periodicity algorithms and a conjecture on overlaps in partial words
- Near-optimal distance emulator for planar graphs
- Computing longest common square subsequences
- Repetitive perhaps, but certainly not boring
- Efficient all path score computations on grid graphs
- Approximate periodicity
- Efficient all path score computations on grid graphs
- Approximate labelled subtree homeomorphism
- Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time
- Shortest-path queries in static networks
- Combinatorics on partial word correlations
- Mining approximate patterns with frequent locally optimal occurrences
- Longest common subsequence problem for unoriented and cyclic strings
- Dynamic RLE-compressed edit distance tables under general weighted cost functions
- Periodic String Comparison
- An all-substrings common subsequence algorithm
- A fully compressed algorithm for computing the edit distance of run-length encoded strings
- Dynamic edit distance table under a general weighted cost function
- A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
- Sequence Alignment Algorithms for Run-Length-Encoded Strings
- A dynamic edit distance table
- Unified compression-based acceleration of edit-distance computation
- Efficient algorithms for finding interleaving relationship between sequences
- Approximate periods of strings
- Implementing approximate regularities
- Two algorithms for LCS consecutive suffix alignment
This page was built for publication: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210080)
