The transposition median problem is NP-complete

DOI10.1016/J.TCS.2010.12.009zbMath1207.68155OpenAlexW2012090438MaRDI 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-completephylogenetic reconstruction algorithmsreversal median problemtransposition distance problemtransposition median problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (2)

Partition–Mallows Model and Its Inference for Rank Aggregation ⋮ On the computational complexity of closest genome problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The transposition median problem is NP-complete