On Complexity of the Subpattern Problem

DOI10.1137/S0895480104444776zbMath1164.68028OpenAlexW2052359455MaRDI QIDQ3629466

Shlomo Ahal, Yuri Rabinovich

Publication date: 27 May 2009

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

Full work available at URL: https://doi.org/10.1137/s0895480104444776

zbMATH Keywords

treewidthpermutationrecognitionforbidden pattern

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (9)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ A linear time algorithm for consecutive permutation pattern matching ⋮ Parity permutation pattern matching ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ Unnamed Item ⋮ Generalized Coloring of Permutations ⋮ Finding and counting permutations via CSPs ⋮ Kernelization lower bound for permutation pattern matching

This page was built for publication: On Complexity of the Subpattern Problem