The transposition median problem is NP-complete

DOI10.1016/J.TCS.2010.12.009MaRDI QIDQ631772zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Reversal and transposition medians
• Combinatorial Pattern Matching
• On the complexity of unsigned translocation distance

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1945189 (Why is no real title available?)
• A Permutation Network
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• Finding an Optimal Inversion Median: Experimental Results
• Genome Rearrangements and Sorting by Reversals
• Median clouds and a fast transposition median solver
• On the cost of interchange rearrangement in strings
• Reversal and transposition medians
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• The NP-Completeness of Some Edge-Partition Problems
• The reversal median problem
• (1+)-approximation of sorting by reversals and transpositions.

Cited in

(7)

• MPF problem over modified medial semigroup is NP-complete
• Two strikes against the phage recombination problem
• Reversal and transposition medians
• On the computational complexity of closest genome problems
• Partition–Mallows Model and Its Inference for Rank Aggregation
• Topology of strings: median string is NP-complete
• Median clouds and a fast transposition median solver

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q631772)