The transposition median problem is NP-complete

DOI10.1016/j.tcs.2010.12.009zbMath1207.68155MaRDI QIDQ631772

Martin Bader

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

zbMATH Keywords

NP-complete; phylogenetic reconstruction algorithms; reversal median problem; transposition distance problem; transposition median problem

Mathematics Subject Classification ID

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