Sorting with two ordered stacks in series.

DOI10.1016/S0304-3975(01)00270-5zbMath1061.68037OpenAlexW2068458438MaRDI QIDQ1853525

Nikola Ruškuc, M. D. Atkinson, Maximillian M. Murphy

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00270-5

zbMATH Keywords

EnumerationPermutationsForbidden patternsStacks

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics in computer science (68R05)

Related Items (12)

2-stack sorting is polynomial ⋮ On the least exponential growth admitting uncountably many closed permutation classes ⋮ Permutations sortable by two stacks in series ⋮ Sorting with networks of data structures ⋮ Two stacks in series: a decreasing stack followed by an increasing stack ⋮ Passing through a stack k times ⋮ Permutations generated by stacks and deques ⋮ Generating permutations with restricted containers ⋮ Enumeration Schemes for Restricted Permutations ⋮ Stack sorting with restricted stacks ⋮ Passing through a stack \(k\) times with reversals ⋮ Permutations generated by a depth 2 stack and an infinite stack in series are algebraic

Cites Work

• Unnamed Item
• Sorting twice through a stack
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• Forbidden subsequences
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Enumeration of planar constellations
• Classification of forbidden subsequences of length 4
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Sorting Using Networks of Queues and Stacks
• A Census of Planar Maps
• Restricted permutations

This page was built for publication: Sorting with two ordered stacks in series.