Pattern matching for permutations

DOI10.1016/S0020-0190(97)00209-3zbMATH Open1338.68304OpenAlexW2083354900WikidataQ55951981 ScholiaQ55951981MaRDI QIDQ293263FDOQ293263

Prosenjit Bose, Jonathan F. Buss, Anna Lubiw

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002093?np=y

Recommendations

• Pattern matching for permutations
• Finding pattern matchings for permutations
• Pattern matching for separable permutations
• On Complexity of the Subpattern Problem
• scientific article; zbMATH DE number 1617282

zbMATH Keywords

algorithmscomputational complexitypermutationpattern matchingseparable permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted permutations
• Complement reducible graphs
• Finding pattern matchings for permutations
• Generating trees and the Catalan and Schröder numbers
• Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
• Stack sortable permutations
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Forbidden subsequences
• A Linear Recognition Algorithm for Cographs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sorting Using Networks of Queues and Stacks
• Title not available (Why is that?)

Cited In (90)

• Determinantal formulas for SEM expansions of Schubert polynomials
• Longest Common Separable Pattern Among Permutations
• The minimum number of monotone subsequences
• On Complexity of the Subpattern Problem
• On the growth of the Möbius function of permutations
• A general exhaustive generation algorithm for Gray structures
• Separable \(d\)-permutations and guillotine partitions
• Product decompositions of the symmetric group induced by separable permutations
• Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem
• On the number of rectangulations of a planar point set
• Kernelization lower bound for permutation pattern matching
• Separable elements and splittings of Weyl groups
• Pattern Matching with Swaps
• Finding common structured patterns in linear graphs
• On the topology of the permutation pattern poset
• The Brownian limit of separable permutations
• Generalized Coloring of Permutations
• Separable elements in Weyl groups
• Permutations avoiding certain patterns: The case of length 4 and some generalizations
• The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size!
• Constructing separable Arnold snakes of Morse polynomials
• Algorithmic and algebraic aspects of unshuffling permutations
• Finding pattern matchings for permutations
• A counterexample regarding labelled well-quasi-ordering
• Pattern matching for permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unsplittable classes of separable permutations
• Order-preserving indexing
• Order-preserving pattern matching with \(k\) mismatches
• A fast algorithm for permutation pattern matching based on alternating runs
• The Möbius function of separable and decomposable permutations
• Sorting with networks of data structures
• A linear time algorithm for consecutive permutation pattern matching
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• Permuted Pattern Matching on Multi-track Strings
• Labelled well-quasi-order for permutation classes
• Parity permutation pattern matching
• Title not available (Why is that?)
• Operators of equivalent sorting power and related Wilf-equivalences
• On the sub-permutations of pattern avoiding permutations
• Multi-Finger Binary Search Trees
• Finding and counting permutations via CSPs
• A bijection between permutations and floorplans, and its applications
• The solution of a conjecture of Stanley and Wilf for all layered patterns
• Title not available (Why is that?)
• On the least exponential growth admitting uncountably many closed permutation classes
• On the Brownian separable permuton
• Parallel algorithms for separable permutations
• On the distribution of the number of occurrences of an order-preserving pattern of length three in a random permutation
• Indexing permutations for binary strings
• Enumeration Schemes for Restricted Permutations
• Sorting by shuffling methods and a queue
• The feasible regions for consecutive patterns of pattern-avoiding permutations
• Algorithms for testing occurrences of length 4 patterns in permutations
• An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem
• Interval posets of permutations
• A polyominoes-permutations injection and tree-like convex polyominoes
• On the longest upsequence problem for permutations
• Pattern matching in the cycle structures of permutations
• Title not available (Why is that?)
• An algorithm computing combinatorial specifications of permutation classes
• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• Title not available (Why is that?)
• Tree enumeration polynomials on separable permutations
• Combinatorial generation via permutation languages. I. Fundamentals
• Order-preserving pattern matching indeterminate strings
• The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements
• Parity permutation pattern matching
• Pattern matching with swaps in practice
• Generalized coloring of permutations
• On the poset of non-attacking King permutations
• Title not available (Why is that?)
• Clustering of consecutive numbers in permutations avoiding a pattern of length three or avoiding a finite number of simple patterns
• Grass(mannian) trees and forests: Variations of the exponential formula, with applications to the momentum amplituhedron
• Computational complexity of counting coincidences
• The skew Brownian permuton: A new universality class for random constrained permutations
• Combinatorics and algorithms for quasi-chain graphs
• Combinatorics and algorithms for quasi-chain graphs
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• The infinite limit of separable permutations
• Complete edge-colored permutation graphs
• Permutations encoding the local shape of level curves of real polynomials via generic projections
• The permuton limit of random recursive separable permutations
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• On the sparseness of the downsets of permutations via their number of separators
• Edit distance between unlabeled ordered trees
• Unknotted cycles
• Distributions of statistics on separable permutations

This page was built for publication: Pattern matching for permutations

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