Abstract
In this work, we consider a restricted case of the well studied Sorting by Block Interchanges problem. We put an upper bound k on the length of the blocks (substrings) to be interchanged at each step. We call the problem Sorting by k-Block Interchanges. We show the problem to be NP-Hard for k=1. The problem is easy for k=n-1, where n is the length of the permutation (the unbounded case). Sorting by Block Interchanges is a very important and widely studied problem with applications in comparative genomics.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.