Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
From MaRDI portal
Publication:3637111
DOI10.1007/978-3-642-02441-2_15zbMath1247.68082MaRDI 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
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W32: Algorithms on strings
Related Items
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