Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
From MaRDI portal
Publication:3637111
DOI10.1007/978-3-642-02441-2_15zbMath1247.68082OpenAlexW1488535707MaRDI QIDQ3637111
Ping-Hui Hsu, Kuan-Yu Chen, Kun-Mao Chao
Publication date: 7 July 2009
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02441-2_15
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Related Items (2)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Recent advances in text-to-pattern distance algorithms
Cites Work
- An improved algorithm for computing the edit distance of run-length coded strings
- Simple deterministic wildcard matching
- Pattern matching with don't cares and few errors
- Computing similarity of run-length encoded strings with affine gap penalty
- Matching for run-length encoded strings
- Inplace run-length 2d compressed search.
- Approximate matching of run-length compressed strings
- Edit distance of run-length encoded strings.
- On a class of \(O(n^ 2)\) problems in computational geometry
- Edit distance for a run-length-encoded string and an uncompressed string
- Subquadratic algorithms for 3SUM
- Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
- Sequence Alignment Algorithms for Run-Length-Encoded Strings
- Verifying candidate matches in sparse and wildcard matching
- Generalized String Matching
- Fast Pattern Matching in Strings
- Fast variable run-length coding for embedded progressive wavelet-based image compression
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- Faster algorithms for string matching with k mismatches
This page was built for publication: Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
