Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-071 | 26th November 1998 00:00

The median problems for breakpoints are NP-complete

RSS-Feed




TR98-071
Authors: Itsik Pe'er, Ron Shamir
Publication: 9th December 1998 13:43
Downloads: 925
Keywords: 


Abstract:

The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint distances to all the original ones. Recently, the
problem was suggested as a model for determining the evolutionary
history of several species based on their gene orders. We show
that the problem is already NP-hard for three permutations, and
that this result holds both for signed and for unsigned
permutations.



ISSN 1433-8092 | Imprint