2-stack sorting is polynomial

DOI10.4230/LIPICS.STACS.2014.614MaRDI QIDQ2965521zbMATH OpenFDO

Authors Adeline Pierrot, Dominique Rossin

Publication date 3 March 2017

Full work available at URL https://arxiv.org/abs/1304.2860

zbMATH Keywords

sortable permutation

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: In this article, we give a polynomial algorithm to decide whether a given permutation $sigma$ is sortable with two stacks in series. This is indeed a longstanding open problem which was first introduced by Knuth. He introduced the stack sorting problem as well as permutation patterns which arises naturally when characterizing permutations that can be sorted with one stack. When several stacks in series are considered, few results are known. There are two main different problems. The first one is the complexity of deciding if a permutation is sortable or not, the second one being the characterization and the enumeration of those sortable permutations. We hereby prove that the first problem lies in P by giving a polynomial algorithm to solve it. This article strongly relies on a previous article in which 2-stack pushall sorting is defined and studied.

Recommendations

• 2-stack sorting is polynomial
• Sorting with two ordered stacks in series.
• Two stacks in series: a decreasing stack followed by an increasing stack
• Two-stack-sorting with pop stacks
• Sorting twice through a stack

Cited in

(6)

• Permutations generated by a depth 2 stack and an infinite stack in series are algebraic
• 2-stack sorting is polynomial
• Permutations sortable by two stacks in series
• Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
• On sorting with a network of two stacks
• Sorting twice through a stack

This page was built for publication: 2-stack sorting is polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965521)