Michael H. Albert ; Marie-Louise Lackner ; Martin Lackner ; Vincent Vatter - The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations

dmtcs:1308 - Discrete Mathematics & Theoretical Computer Science, December 21, 2016, Vol. 18 no. 2, Permutation Patterns 2015 - https://doi.org/10.46298/dmtcs.1308
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged PermutationsArticle

Authors: Michael H. Albert ; Marie-Louise Lackner ; Martin Lackner ; Vincent Vatter ORCID

    The Permutation Pattern Matching problem, asking whether a pattern permutation $\pi$ is contained in a permutation $\tau$, is known to be NP-complete. In this paper we present two polynomial time algorithms for special cases. The first algorithm is applicable if both $\pi$ and $\tau$ are $321$-avoiding; the second is applicable if $\pi$ and $\tau$ are skew-merged. Both algorithms have a runtime of $O(kn)$, where $k$ is the length of $\pi$ and $n$ the length of $\tau$.


    Volume: Vol. 18 no. 2, Permutation Patterns 2015
    Section: Permutation Patterns
    Published on: December 21, 2016
    Accepted on: December 21, 2016
    Submitted on: December 21, 2016
    Keywords: Mathematics - Combinatorics,Computer Science - Data Structures and Algorithms,05A05, 68Q25
    Funding:
      Source : OpenAIRE Graph
    • Fixed-Parameter Tractability in Artificial Intelligence and Reasoning (FAIR); Code: P 25518
    • Decodyn: Treating Hard Problems with Decomposition and Dynamic Programming; Code: Y 698
    • Algorithms for Complex Collective Decisions on Structured Domains; Funder: European Commission; Code: 639945
    • The Structure of Permutation Classes; Funder: National Science Foundation; Code: 1301692
    • Restricted labelled combinatorial objects; Funder: National Science Foundation; Code: P 25337

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1101 times.
    This article's PDF has been downloaded 503 times.