On the complexity of the sub-permutation problem

DOI10.1007/3-540-44985-X_41MaRDI QIDQ2722006zbMATH OpenFDO

Authors Shlomo Ahal, Yuri Rabinovich

Publication date 11 July 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44985-X_41

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On Complexity of the Subpattern Problem
• Pattern matching for permutations
• Pattern matching for permutations
• Finding and counting permutations via CSPs
• Finding and Counting Permutations via CSPs

Cited in

(13)

• On minimum \(k\)-modal partitions of permutations
• Inclusion relationships among permutation problems
• On the least exponential growth admitting uncountably many closed permutation classes
• Simple permutations: Decidability and unavoidable substructures
• Pattern matching for permutations
• Solving a permutation problem by a fully polynomial-time approximation scheme
• On Minimum k-Modal Partitions of Permutations
• On Complexity of the Subpattern Problem
• scientific article; zbMATH DE number 4053621 (Why is no real title available?)
• scientific article; zbMATH DE number 1998299 (Why is no real title available?)
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• A space-time tradeoff for permutation problems
• The complexity of finding SUBSEQ(A)

This page was built for publication: On the complexity of the sub-permutation problem

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