A New Tight Upper Bound on the Transposition Distance | Zendy

Anthony Labarre | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A New Tight Upper Bound on the Transposition Distance

Author(s) -

Anthony Labarre

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-29008-7

DOI - 10.1007/11557067_18

Subject(s) - transposition (logic) , permutation (music) , upper and lower bounds , combinatorics , computer science , permutation graph , random permutation , permutation group , class (philosophy) , discrete mathematics , block (permutation group theory) , mathematics , graph , physics , mathematical analysis , artificial intelligence , acoustics

We study the problem of computing the minimal number of adjacent, non-intersecting block interchanges required to transform a permutation into the identity permutation. In particular, we use the graph of a permutation to compute that number for a particular class of permutations in linear time and space, and derive a new tight upper bound on the so-called transposition distance. © Springer-Verlag Berlin Heidelberg 2005.SCOPUS: cp.kinfo:eu-repo/semantics/publishe

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research