Hardness of comparing two run-length encoded strings
From MaRDI portal
Publication:990818
DOI10.1016/J.JCO.2010.03.003zbMATH Open1193.94077OpenAlexW2009278392MaRDI QIDQ990818FDOQ990818
Authors: Kuan-Yu Chen, Ping-Hui Hsu, Kun-Mao Chao 
Publication date: 1 September 2010
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2010.03.003
Recommendations
- An algorithm for matching run-length coded strings
- Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
- Almost linear time computation of maximal repetitions in run length encoded strings
- Matching for run-length encoded strings
- Approximate matching of run-length compressed strings
- scientific article; zbMATH DE number 1786446
- Computing similarity of run-length encoded strings with affine gap penalty
- Parallel comparison of run-length-encoded strings on a linear systolic array
Cites Work
- On a class of \(O(n^ 2)\) problems in computational geometry
- Matching for run-length encoded strings
- Approximate matching of run-length compressed strings
- Generalized String Matching
- Title not available (Why is that?)
- Faster algorithms for string matching with k mismatches
- Simple deterministic wildcard matching
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Title not available (Why is that?)
- Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- Matching patterns in strings subject to multi-linear transformations
- Edit distance for a run-length-encoded string and an uncompressed string
- Inplace run-length 2d compressed search.
- Sequence Alignment Algorithms for Run-Length-Encoded Strings
Cited In (6)
- Efficient retrieval of approximate palindromes in a run-length encoded string
- A fully compressed algorithm for computing the edit distance of run-length encoded strings
- Gel'fand-\(N\)-width in probabilistic setting
- R\'enyi entropy and pattern matching for run-length encoded sequences
- Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
- Approximation of functions on the sphere on a Sobolev space with a Gaussian measure in the probabilistic case setting
This page was built for publication: Hardness of comparing two run-length encoded strings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990818)
