Efficient all path score computations on grid graphs
DOI10.1016/J.TCS.2013.07.018zbMATH Open1282.68204OpenAlexW2167537982MaRDI QIDQ2437757FDOQ2437757
Dekel Tsur, Michal Ziv-Ukelson, Ury Matarazzo
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.018
Recommendations
- Efficient all path score computations on grid graphs
- On almost Monge all scores matrices
- scientific article; zbMATH DE number 6792426
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- A linear-time algorithm for the longest path problem in rectangular grid graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Paths and cycles (05C38) Algorithms on strings (68W32)
Cites Work
- The String-to-String Correction Problem
- Efficient Parallel Algorithms for String Editing and Related Problems
- On the common substring alignment problem
- Incremental String Comparison
- Two algorithms for LCS consecutive suffix alignment
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Semi-local longest common subsequences in subquadratic time
- Title not available (Why is that?)
- Semi-local string comparison: algorithmic techniques and applications
- An all-substrings common subsequence algorithm
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Fundamentals of Computation Theory
- A dynamic edit distance table
- New clique and independent set algorithms for circle graphs
- An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
- A space efficient algorithm for finding the best nonoverlapping alignment score
- Sparse LCS common substring alignment
- Title not available (Why is that?)
- Title not available (Why is that?)
- Periodic String Comparison
Cited In (2)
This page was built for publication: Efficient all path score computations on grid graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437757)
