Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SIGNED PERMUTATIONS:
Reports tagged with signed permutations:
TR98-071 | 26th November 1998
Itsik Pe'er, Ron Shamir

The median problems for breakpoints are NP-complete

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 ... more >>>




ISSN 1433-8092 | Imprint