arXiv Open Access 2020

Sorting by Prefix Block-Interchanges

Anthony Labarre

Lihat Sumber

Abstrak

We initiate the study of sorting permutations using prefix block-interchanges, which exchange any prefix of a permutation with another non-intersecting interval. The goal is to transform a given permutation into the identity permutation using as few such operations as possible. We give a 2-approximation algorithm for this problem, show how to obtain improved lower and upper bounds on the corresponding distance, and determine the largest possible value for that distance.

Topik & Kata Kunci

cs.DS

Penulis (1)

Anthony Labarre

Format Sitasi

APA MLA BibTeX

Labarre, A. (2020). Sorting by Prefix Block-Interchanges. https://arxiv.org/abs/2008.13640

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓