Publication Type:

Book Chapter

Source:

Advances in Computational Biology, Springer New York, New York, NY, p.725–736 (2010)

ISBN:

9781441959133

URL:

https://doi.org/10.1007/978-1-4419-5913-3_81

Abstract:

A k-bounded (k ≥ 2) transposition is an operation that switches two elements that have at most k − 2 elements in between. We study the problem of sorting a circular permutation $π$ of length n for k = 2, i.e., adjacent swaps and k = 3, i.e., short swaps. These transpositions mimic microrearrangements of gene order in viruses and bacteria. We prove a (1/4)n 2 lower bound for sorting by adjacent swaps. We show upper bounds of (5/32)n 2 + O(n log n) and (7/8)n + O(log n) for sequential and parallel sorting, respectively, by short swaps.

Cite this Research Publication

X. Feng, Dr. Bhadrachalam Chitturi, and Sudborough, H., “Sorting Circular Permutations by Bounded Transpositions”, in Advances in Computational Biology, H. R. Arabnia New York, NY: Springer New York, 2010, pp. 725–736.

207
PROGRAMS
OFFERED
6
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS