The consensus string problem for a metric is NP-complete
From MaRDI portal
Publication:876700
DOI10.1016/S1570-8667(03)00011-XzbMath1118.68449MaRDI QIDQ876700
Publication date: 26 April 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
Efficient approaches for the flooding problem on graphs ⋮ Hybridizations of Metaheuristics With Branch & Bound Derivates ⋮ Ensemble clustering by means of clustering embedding in vector spaces ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ The Contig Assembly Problem and Its Algorithmic Solutions ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Closest substring problems for regular languages ⋮ Consensus string problem for multiple regular languages ⋮ Hardness results for the center and median string problems under the weighted and unweighted edit distances ⋮ Tractability and hardness of flood-filling games on trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On covering problems of codes
- The shortest common supersequence problem over binary alphabet is NP- complete
- Efficient methods for multiple sequence alignment with guaranteed error bounds
- More on the complexity of common superstring and supersequence problems
- Approximation algorithms for tree alignment with a given phylogeny
- Finding similar regions in many strings
- Trees, Stars, and Multiple Biological Sequence Alignment
- The Complexity of Some Problems on Subsequences and Supersequences
- Algorithms on Strings, Trees and Sequences
- Mapping the genome
This page was built for publication: The consensus string problem for a metric is NP-complete
