The transposition median problem is NP-complete
DOI10.1016/J.TCS.2010.12.009zbMATH Open1207.68155OpenAlexW2012090438MaRDI QIDQ631772FDOQ631772
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
Recommendations
NP-completephylogenetic reconstruction algorithmsreversal median problemtransposition distance problemtransposition median problem
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Cites Work
- Title not available (Why is that?)
- The reversal median problem
- Sorting by Transpositions
- The NP-Completeness of Some Edge-Partition Problems
- Disjoint Cycles: Integrality Gap, Hardness, and Approximation
- Sorting Permutations by Reversals and Eulerian Cycle Decompositions
- Genome Rearrangements and Sorting by Reversals
- On the cost of interchange rearrangement in strings
- \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
- A Permutation Network
- A simpler and faster 1.5-approximation algorithm for sorting by transpositions
- Reversal and transposition medians
- Median clouds and a fast transposition median solver
- Title not available (Why is that?)
- Finding an Optimal Inversion Median: Experimental Results
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)
