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
Y1 - 2010
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 -