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

DOI10.1007/978-3-642-02441-2_15MaRDI QIDQ3637111zbMATH OpenOpenAlexFDO

Authors Kuan-Yu Chen, Ping-Hui Hsu, 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

3sum\(k\)-mismatchesalignmentrun-length encodingwildcard matching

Mathematics Subject Classification ID

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)

Recommendations

• Approximate matching of run-length compressed strings
• scientific article; zbMATH DE number 1786446
• Hardness of comparing two run-length encoded strings
• Parameterized searching with mismatches for run-length encoded strings
• An algorithm for matching run-length coded strings
• Almost linear time computation of maximal repetitions in run length encoded strings
• scientific article; zbMATH DE number 1256698
• Matching for run-length encoded strings

Cites work

• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• An improved algorithm for computing the edit distance of run-length coded strings
• Approximate matching of run-length compressed strings
• Computing similarity of run-length encoded strings with affine gap penalty
• Edit distance for a run-length-encoded string and an uncompressed string
• Edit distance of run-length encoded strings.
• Fast Pattern Matching in Strings
• Fast variable run-length coding for embedded progressive wavelet-based image compression
• Faster algorithms for string matching with k mismatches
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Generalized String Matching
• Inplace run-length 2d compressed search.
• Matching for run-length encoded strings
• On a class of \(O(n^ 2)\) problems in computational geometry
• Pattern matching with don't cares and few errors
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Simple deterministic wildcard matching
• Subquadratic algorithms for 3SUM
• Verifying candidate matches in sparse and wildcard matching

Cited in

(5)

• Three one-way heads cannot do string matching
• Recent advances in text-to-pattern distance algorithms
• Identifying approximate palindromes in run-length encoded strings
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Hardness of comparing two run-length encoded strings

This page was built for publication: Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637111)