TY - GEN

T1 - A graphical model for computing the minimum cost transposition distance

AU - Farnoud, Farzad

AU - Chen, Chien Yu

AU - Milenkovic, Olgica

AU - Kashyap, Navin

PY - 2010/12/1

Y1 - 2010/12/1

N2 - We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. For metric-path costs, we describe exact polynomial-time decomposition algorithms. For extended-metric-path cost functions, we describe polynomial-time constant-approximation decomposition algorithms. Our algorithms rely on graphical representations of permutations and graph-search techniques for minimizing the permutation decomposition cost. The presented algorithms have applications in information theory, bioinformatics, and algebra.

AB - We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. For metric-path costs, we describe exact polynomial-time decomposition algorithms. For extended-metric-path cost functions, we describe polynomial-time constant-approximation decomposition algorithms. Our algorithms rely on graphical representations of permutations and graph-search techniques for minimizing the permutation decomposition cost. The presented algorithms have applications in information theory, bioinformatics, and algebra.

UR - http://www.scopus.com/inward/record.url?scp=80051931370&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80051931370&partnerID=8YFLogxK

U2 - 10.1109/CIG.2010.5592890

DO - 10.1109/CIG.2010.5592890

M3 - Conference contribution

AN - SCOPUS:80051931370

SN - 9781424482641

T3 - 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings

BT - 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings

T2 - 2010 IEEE Information Theory Workshop, ITW 2010

Y2 - 30 August 2010 through 3 September 2010

ER -