2-Stack Sorting is Polynomial

In this article, we give a polynomial algorithm to decide whether a given permutation σ is sortable with two stacks in series. This is indeed a longstanding open problem which was first introduced by Knuth ([ 1973 ]). He introduced the stack sorting problem as well as permutation patterns which aris...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2017-04, Vol.60 (3), p.552-579
Main Authors: Pierrot, Adeline, Rossin, Dominique
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Combinatorics
Complexity
Computation
Computer programming
Computer Science
Enumeration
Graphs
Permutations
Polynomials
Sorting
Stacks
Studies
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article, we give a polynomial algorithm to decide whether a given permutation σ is sortable with two stacks in series. This is indeed a longstanding open problem which was first introduced by Knuth ([ 1973 ]). 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 relies on Pierrot and Rossin ([ 2013 ]) in which 2-stack pushall sorting is defined and studied.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-016-9743-8