Finding small patterns in permutations in linear time

DOI10.1137/1.9781611973402.7zbMath1421.68083arXiv1307.3073OpenAlexW2950143318WikidataQ60638484 ScholiaQ60638484MaRDI QIDQ5383966

Dániel Marx, Sylvain Guillemot

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.3073

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05)

Related Items (16)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Order-preserving indexing ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Twin-width II: small classes ⋮ Parity permutation pattern matching ⋮ Improved algorithm for permutation testing ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Generalized Coloring of Permutations ⋮ Unnamed Item ⋮ On the structure of matrices avoiding interval-minor patterns ⋮ Finding and counting permutations via CSPs ⋮ Twin-width and generalized coloring numbers ⋮ Kernelization lower bound for permutation pattern matching ⋮ Combinatorial generation via permutation languages. I. Fundamentals

This page was built for publication: Finding small patterns in permutations in linear time