On the hardness of the consensus string problem
From MaRDI portal
Publication:396596
DOI10.1016/j.ipl.2013.02.016zbMath1371.68093OpenAlexW1975226991MaRDI QIDQ396596
Amihood Amir, Haim Paryenty, Liam Roditty
Publication date: 13 August 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2013.02.016
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Related Items (6)
Two-string consensus problem under non-overlapping inversion and transposition distance ⋮ On the string consensus problem and the Manhattan sequence consensus problem ⋮ An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Closest substring problems for regular languages ⋮ Consensus string problem for multiple regular languages
Cites Work
- Unnamed Item
- Unnamed Item
- A three-string approach to the closest string problem
- On covering problems of codes
- Pattern matching with address errors: rearrangement distances
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Optimal Solutions for the Closest-String Problem via Integer Programming
- Two Algorithms for the Minimum Enclosing Ball Problem
- String Rearrangement Metrics: A Survey
- More Efficient Algorithms for Closest String and Substring Problems
- An Extension of the String-to-String Correction Problem
- Pattern Matching with Swaps
- Configurations and Minority in the String Consensus Problem
- Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
- On the spherical surface of smallest radius enclosing a bounded subset of 𝑛-dimensional euclidean space
This page was built for publication: On the hardness of the consensus string problem