On the hardness of the consensus string problem

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

zbMATH Keywords

computational complexitycombinatorial problemsHamming distanceconsensusswapreversal

Mathematics Subject Classification ID

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