### 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 language | English (US) |
---|---|

Title of host publication | 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings |

DOIs | |

State | Published - Dec 1 2010 |

Event | 2010 IEEE Information Theory Workshop, ITW 2010 - Dublin, Ireland Duration: Aug 30 2010 → Sep 3 2010 |

### Publication series

Name | 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings |
---|

### Other

Other | 2010 IEEE Information Theory Workshop, ITW 2010 |
---|---|

Country | Ireland |

City | Dublin |

Period | 8/30/10 → 9/3/10 |

### ASJC Scopus subject areas

- Information Systems
- Applied Mathematics

## Fingerprint Dive into the research topics of 'A graphical model for computing the minimum cost transposition distance'. Together they form a unique fingerprint.

## 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