2-stack sorting is polynomial

DOI10.1007/s00224-016-9743-8zbMath1429.68055OpenAlexW1781970429MaRDI QIDQ2363966

Dominique Rossin, Adeline Pierrot

Publication date: 17 July 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-016-9743-8

zbMATH Keywords

combinatoricspolynomial algorithmpermutation patternsstack-sorting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05)

Related Items (3)

Dynamical aspects of \(\sigma\)-machines ⋮ Stack sorting with increasing and decreasing stacks ⋮ Passing through a stack \(k\) times with reversals

Cites Work

• Unnamed Item
• Unnamed Item
• Patterns in permutations and words.
• Permutations generated by stacks and deques
• Sorting twice through a stack
• A survey of stack-sorting disciplines
• Sorting with two ordered stacks in series.
• The complexity of colouring circle graphs
• Sorting Using Networks of Queues and Stacks

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