Publication Type:

Journal Article

Source:

Theoretical Computer Science, Elsevier, Volume 421, p.15–24 (2012)

URL:

http://www.sciencedirect.com/science/article/pii/S0304397511009376

Abstract:

A transposition is an operation that exchanges two adjacent substrings. Transpositions over permutations, the sequences with no repeated symbols, are related to genome rearrangements. If one of the substrings is restricted to a prefix then it is called a prefix transposition. The prefix transposition distance between a pair of strings (permutations) is the minimum number of prefix transpositions required to transform a given string (permutation) into another given string (permutation). For a permutation of length n, we improve the current prefix transposition distance upper bound of n−log8n to n−log9/2n. For arbitrary strings, we prove new prefix transposition distance upper and lower bounds. For binary strings of length n, we show that n/2 is an upper bound. We show that the prefix transposition distance problem is NP-complete for binary strings.

Notes:

cited By (since 1996)2

Cite this Research Publication

Dr. Bhadrachalam Chitturi and I Sudborough, H., “Bounding prefix transposition distance for strings and permutations”, Theoretical Computer Science, vol. 421, pp. 15–24, 2012.

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