A survey of stack-sorting disciplines

MaRDI QIDQ1408520zbMATH OpenFDO

Authors Miklós Bóna

Publication date 24 September 2003

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/123106, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i2a1.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Review text

Summary: We review the various ways that stacks, their variations and their combinations, have been used as sorting devices. In particular, we show that they have been a key motivator for the study of permutation patterns. We also show that they have connections to other areas in combinatorics such as Young tableau, planar graph theory, and simplicial complexes.

Recommendations

• A survey of stack sortable permutations
• Comparing algorithms for sorting with t stacks in series
• Sorting with Complete Networks of Stacks
• Stack-sortable permutations and beyond
• Flip-sort and combinatorial aspects of pop-stack sorting
• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack sorting with restricted stacks
• Stack-sorting, set partitions, and Lassalle's sequence
• scientific article; zbMATH DE number 3878372
• The Complexity of Sorting with Networks of Stacks and Queues

Cited in

(64)

• On minimum \(k\)-modal partitions of permutations
• Inglenook shunting puzzles
• A simplicial complex of 2-stack sortable permutations
• Sorting with a forklift
• Comparing algorithms for sorting with t stacks in series
• Further bijections to pattern-avoiding valid hook configurations
• Asymptotics of 3-stack-sortable permutations
• Stack-sorting with consecutive-pattern-avoiding stacks
• Finding and counting permutations via CSPs
• Meeting covered elements in -Tamari lattices
• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting
• Sorting by shuffling methods and a queue
• Catalan intervals and uniquely sorted permutations
• Polyurethane toggles
• Stack-sorting preimages of permutation classes
• Uniquely sorted permutations
• Quantifying noninvertibility in discrete dynamical systems
• Fertility monotonicity and average complexity of the stack-sorting map
• Stack sorting with increasing and decreasing stacks
• Counting 3-stack-sortable permutations
• Passing through a stack \(k\) times with reversals
• Preimages under the stack-sorting algorithm
• 2-stack sorting is polynomial
• A unified approach to polynomial sequences with only real zeros
• How to sort by walking and swapping on paths and trees
• Bubblesort, stacksort and their duals
• Actions on permutations and unimodality of descent polynomials
• Simple permutations: Decidability and unavoidable substructures
• Lattice paths and \((n - 2)\)-stack sortable permutations
• The parallel stack loading problem to minimize blockages
• New equivalences for pattern avoiding involutions
• Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
• Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
• Permutations sortable by two stacks in parallel and quarter plane walks
• Passing through a stack k times
• Sorting Cayley permutations with pattern-avoiding machines
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Flip-sort and combinatorial aspects of pop-stack sorting
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Highly sorted permutations and Bell numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• A survey of stack sortable permutations
• Asymptotic normality in t-stack sortable permutations
• Sorting and preimages of pattern classes
• On linear transformations preserving the Pólya frequency property
• Permutree sorting
• Permutree sorting
• Sorting with networks of data structures
• Dynamical aspects of \(\sigma\)-machines
• Troupes, cumulants, and stack-sorting
• A lift of West's stack-sorting map to partition diagrams
• Sorting via shuffles with a cut after the longest increasing prefix
• Foot-sorting for socks
• Deterministic stack-sorting for set partitions
• Dynamics of pop-tsack torsing
• Periodic points of consecutive-pattern-avoiding stack-sorting maps
• Cyclic-pattern-avoiding stacks
• Stack-sorting with stacks avoiding vincular patterns
• The parallel stack loading problem: polynomial solvability in the unlimited-capacity case and exact approaches for the finite-capacity case
• Stack-sorting, set partitions, and Lassalle's sequence
• Permuting machines and priority queues

This page was built for publication: A survey of stack-sorting disciplines

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