On the hardness of the consensus string problem
From MaRDI portal
Publication:396596
DOI10.1016/J.IPL.2013.02.016zbMATH Open1371.68093OpenAlexW1975226991MaRDI QIDQ396596FDOQ396596
Authors: 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
Recommendations
- The consensus string problem for a metric is NP-complete
- On the Efficiency of the Hamming C-Centerstring Problems
- Tight hardness results for consensus problems on circular strings and time series
- Efficient algorithms for consensus string problems minimizing both distance sum and radius
- Finding similar regions in many strings
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Cites Work
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Optimal solutions for the closest-string problem via integer programming
- More efficient algorithms for closest string and substring problems
- A three-string approach to the closest string problem
- Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
- Title not available (Why is that?)
- On covering problems of codes
- Two Algorithms for the Minimum Enclosing Ball Problem
- Title not available (Why is that?)
- An Extension of the String-to-String Correction Problem
- Pattern Matching with Swaps
- On the spherical surface of smallest radius enclosing a bounded subset of 𝑛-dimensional euclidean space
- String rearrangement metrics: a survey
- Configurations and minority in the string consensus problem
- Pattern matching with address errors: rearrangement distances
Cited In (8)
- Closest substring problems for regular languages
- The consensus string problem for a metric is NP-complete
- On the string consensus problem and the Manhattan sequence consensus problem
- Consensus string problem for multiple regular languages
- Tight hardness results for consensus problems on circular strings and time series
- Two-string consensus problem under non-overlapping inversion and transposition distance
- An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications
- Consensus string problem for multiple regular languages
This page was built for publication: On the hardness of the consensus string problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396596)
