On Complexity of the Subpattern Problem

DOI10.1137/S0895480104444776MaRDI QIDQ3629466zbMATH OpenOpenAlexFDO

Authors 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

forbidden patternpermutationrecognitiontreewidth

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1617282
• Hardness of permutation pattern matching
• Pattern matching for permutations
• Finding small patterns in permutations in linear time
• Pattern matching for permutations

Cited in

(21)

• Finding and counting permutations via CSPs
• Kernelization lower bound for permutation pattern matching
• scientific article; zbMATH DE number 1617282 (Why is no real title available?)
• The complexity of counting poset and permutation patterns
• Pattern matching for permutations
• The computational landscape of permutation patterns
• scientific article; zbMATH DE number 4053621 (Why is no real title available?)
• A linear time algorithm for consecutive permutation pattern matching
• scientific article; zbMATH DE number 1998299 (Why is no real title available?)
• Hardness of permutation pattern matching
• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• Generalized Coloring of Permutations
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Finding small patterns in permutations in linear time
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Parity permutation pattern matching
• Strongly sublinear algorithms for testing pattern freeness
• Generalized coloring of permutations
• Parity permutation pattern matching
• Counting permutation patterns with multidimensional trees
• The complexity of finding SUBSEQ(A)

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

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