The transposition median problem is NP-complete
From MaRDI portal
Publication:631772
DOI10.1016/j.tcs.2010.12.009zbMath1207.68155MaRDI QIDQ631772
Publication date: 14 March 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.12.009
NP-complete; phylogenetic reconstruction algorithms; reversal median problem; transposition distance problem; transposition median problem
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W32: Algorithms on strings
Related Items
Partition–Mallows Model and Its Inference for Rank Aggregation, On the computational complexity of closest genome problems
Cites Work
- Reversal and transposition medians
- \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
- A simpler and faster 1.5-approximation algorithm for sorting by transpositions
- The Reversal Median Problem
- Disjoint Cycles: Integrality Gap, Hardness, and Approximation
- The NP-Completeness of Some Edge-Partition Problems
- Sorting Permutations by Reversals and Eulerian Cycle Decompositions
- Sorting by Transpositions
- Finding an Optimal Inversion Median: Experimental Results
- Genome Rearrangements and Sorting by Reversals
- A Permutation Network
- On the Cost of Interchange Rearrangement in Strings
- Unnamed Item
- Unnamed Item
- Unnamed Item