Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

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

zbMATH Keywords

alignment; run-length encoding; wildcard matching; \(k\)-mismatches; 3sum

Mathematics Subject Classification ID

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