Stack sortable permutations

DOI10.1016/0012-365X(81)90165-5zbMath0497.05003MaRDI QIDQ1170191

Doron Rotem

Publication date: 1981

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

binary treescomparability graphspermutation graphmonotonic subsequencesnested interval graph

Mathematics Subject Classification ID

Trees (05C05) Permutations, words, matrices (05A05) Graph theory (05C99)

Related Items (18)

Pattern matching for permutations ⋮ Order-preserving indexing ⋮ CONSTANT-MEMORY ITERATIVE GENERATION OF SPECIAL STRINGS REPRESENTING BINARY TREES ⋮ The Euler-Catalan identity ⋮ Coding Binary Trees by Words over an Alphabet with Four Letters ⋮ A linear time algorithm for consecutive permutation pattern matching ⋮ Generating binary trees in A-order from codewords defined on a four-letter alphabet ⋮ Noncontiguous pattern containment in binary trees ⋮ Unnamed Item ⋮ Pattern matching for permutations ⋮ Restricted permutations ⋮ q-Enumeration of alternating permutations of odd length ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Passing through a stack \(k\) times with reversals ⋮ A combinatorial proof of J. West's conjecture ⋮ Kernelization lower bound for permutation pattern matching ⋮ Permutation representation of k-ary trees

Cites Work

• Unnamed Item
• On a correspondence between binary trees and a certain type of permutation
• Natural Sorting
• Generation of Binary Trees from Ballot Sequences
• A Note on "The Comparability Graph of a Tree"
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: Stack sortable permutations