English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A number of fields, including the study of genome rearrangements and thedesign of interconnection networks, deal with the connected problems of sortingpermutations in "as few moves as possible", using a given set of allowedoperations, or computing the number of moves the sorting process requires,often referred to as the \emph{distance} of the permutation. These operationsoften act on just one or two segments of the permutation, e.g. by reversing onesegment or exchanging two segments. The \emph{cycle graph} of the permutationto sort is a fundamental tool in the theory of genome rearrangements, and hasproved useful in settling the complexity of many variants of the aboveproblems. In this paper, we present an algebraic reinterpretation of the cyclegraph of a permutation $\pi$ as an even permutation $\bar{\pi}$, and show howto reformulate our sorting problems in terms of particular factorisations ofthe latter permutation. Using our framework, we recover known results in asimple and unified way, and obtain a new lower bound on the \emph{prefixtransposition distance} (where a \emph{prefix transposition} displaces theinitial segment of a permutation), which is shown to outperform previousresults. Moreover, we use our approach to improve the best known lower bound onthe \emph{prefix transposition diameter} from $2n/3$ to $\lfloor3n/4\rfloor$,and investigate a few relations between some statistics on $\pi$ and$\bar{\pi}$.

Lower bounding edit distances between permutations