A graphical model for computing the minimum cost transposition distance

Farzad Farnoud, Chien Yu Chen, Olgica Milenkovic, Navin Kashyap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings
DOIs
StatePublished - Dec 1 2010
Event2010 IEEE Information Theory Workshop, ITW 2010 - Dublin, Ireland
Duration: Aug 30 2010Sep 3 2010

Publication series

Name2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings

Other

Other2010 IEEE Information Theory Workshop, ITW 2010
CountryIreland
CityDublin
Period8/30/109/3/10

    Fingerprint

ASJC Scopus subject areas

  • Information Systems
  • Applied Mathematics

Cite this

Farnoud, F., Chen, C. Y., Milenkovic, O., & Kashyap, N. (2010). A graphical model for computing the minimum cost transposition distance. In 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings [5592890] (2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings). https://doi.org/10.1109/CIG.2010.5592890