Comparing algorithms for sorting with t stacks in series

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that the left-greedy algorithm is a better algorithm than the right-greedy algorithm for sorting permutations using t stacks in series when t>1. We also supply a method for constructing some permutations that can be sorted by t stacks in series and from this get a lower bound on the number of permutations of length n that are sortable by t stacks in series. Finally we show that the left-greedy algorithm is neither optimal nor defines a closed class of permutations for t>2.
9 pages, 7 figures, To be published in Annals of Combinatorics. The new version makes a few grammatical changes, clarifies a definition, and fixes the figures

Keywords

Combinatorics, 05A05 (primary), 68R05, 68W01 (secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/70800

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0404176
 http://arxiv.org/abs/math/0404176

Collections

arXiv