Advancing the Transposition Distance and Diameter through Lonely Permutations

DOI10.1137/120899753zbMath1307.05002OpenAlexW2071284458MaRDI QIDQ5408585

Luís Cunha, Rodrigo A. Hausen, Luis Antonio B. Kowada, Celina M. Herrera de Figueiredo

Publication date: 10 April 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120899753

zbMATH Keywords

genome rearrangementssorting by transpositionstransposition diameterknot permutationslonely permutations

Mathematics Subject Classification ID

Searching and sorting (68P10) Problems related to evolution (92D15) Applications of graph theory (05C90) Combinatorics on words (68R15) Permutations, words, matrices (05A05) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Group actions on combinatorial structures (05E18)

Related Items (3)

Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs ⋮ Hardness and efficiency on minimizing maximum distances in spanning trees ⋮ On the computational complexity of closest genome problems

This page was built for publication: Advancing the Transposition Distance and Diameter through Lonely Permutations