{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297421,"version":"3.37.3"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ERC","award":["725978"],"award-info":[{"award-number":["725978"]}]},{"name":"DFG","award":["KO 6140\/1-1"],"award-info":[{"award-number":["KO 6140\/1-1"]}]},{"DOI":"10.13039\/501100007537","name":"Freie Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007537","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of lengthn<\/jats:italic>contains a given pattern of lengthk<\/jats:italic>. In this work we give two new algorithms for this well-studied problem, one whose running time is$$n^{k\/4 + o(k)}$$<\/jats:tex-math>n<\/mml:mi>k<\/mml:mi>\/<\/mml:mo>4<\/mml:mn>+<\/mml:mo>o<\/mml:mi>(<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a polynomial-space algorithm whose running time is the better of$$O(1.6181^n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>.<\/mml:mo>6181<\/mml:mn>n<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$O(n^{k\/2 + 1})$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>k<\/mml:mi>\/<\/mml:mo>2<\/mml:mn>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. These results improve the earlier best bounds of$$n^{0.47k + o(k)}$$<\/jats:tex-math>n<\/mml:mi>0.47<\/mml:mn>k<\/mml:mi>+<\/mml:mo>o<\/mml:mi>(<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$O(1.79^n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>.<\/mml:mo>79<\/mml:mn>n<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when$$k \\in \\varOmega (\\log {n})$$<\/jats:tex-math>k<\/mml:mi>\u2208<\/mml:mo>\u03a9<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens ofconstraint-satisfaction<\/jats:italic>. Our algorithms can alsocount<\/jats:italic>, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time$$f(k) \\cdot n^{o(k\/\\log {k})}$$<\/jats:tex-math>f<\/mml:mi>(<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:mrow>\u00b7<\/mml:mo>n<\/mml:mi>o<\/mml:mi>(<\/mml:mo>k<\/mml:mi>\/<\/mml:mo>log<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>would contradict theexponential-time hypothesis<\/jats:italic>(ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing<\/jats:italic>(4321-avoiding) and 3-decreasing<\/jats:italic>(1234-avoiding) permutations can, in some sense,embed<\/jats:italic>arbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes.<\/jats:p>","DOI":"10.1007\/s00453-021-00812-z","type":"journal-article","created":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T05:02:52Z","timestamp":1614574972000},"page":"2552-2577","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Finding and Counting Permutations via CSPs"],"prefix":"10.1007","volume":"83","author":[{"given":"Benjamin Aram","family":"Berendsohn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e1szl\u00f3","family":"Kozma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,1]]},"reference":[{"issue":"2","key":"812_CR1","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/S0895480104444776","volume":"22","author":"S Ahal","year":"2008","unstructured":"Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM J. Discrete Math. 22(2), 629\u2013649 (2008)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"812_CR2","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.jcta.2005.02.006","volume":"112","author":"MH Albert","year":"2005","unstructured":"Albert, M.H., Paterson, M.S.: Bounds for the growth rate of meander numbers. J. Comb. Theory Ser. A 112(2), 250\u2013262 (2005)","journal-title":"J. Comb. Theory Ser. A"},{"key":"812_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.ejc.2014.08.024","volume":"43","author":"M Albert","year":"2015","unstructured":"Albert, M., Bousquet-M\u00e9lou, M.: Permutations sortable by two stacks in parallel and quarter plane walks. Eur. J. Comb. 43, 131\u2013164 (2015)","journal-title":"Eur. J. Comb."},{"doi-asserted-by":"crossref","unstructured":"Albert, M.H., Aldred, R.E.L., Atkinson, M.D., Holton, D.A.: Algorithms for pattern involvement in permutations. In: Proceedings of the 12th International Symposium on Algorithms and Computation, ISAAC \u201901, pp. 355\u2013366, Springer-Verlag, London, UK (2001)","key":"812_CR4","DOI":"10.1007\/3-540-45678-3_31"},{"key":"812_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.jcta.2018.02.006","volume":"157","author":"MH Albert","year":"2018","unstructured":"Albert, M.H., Homberger, C., Pantone, J., Shar, N., Vatter, V.: Generating permutations with restricted containers. J. Comb. Theory Ser. A 157, 205\u2013232 (2018)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"2","key":"812_CR6","first-page":"1","volume":"18","author":"MH Albert","year":"2016","unstructured":"Albert, M.H., Lackner, M.-L., Lackner, M., Vatter, V.: The complexity of pattern matching for 321-avoiding and skew-merged permutations. Discrete Math. Theor. Comput. Sci. 18(2), 1\u201317 (2016)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"812_CR7","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D Aldous","year":"1999","unstructured":"Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the baik-deift-johansson theorem. Bull. Am. Math. Soc 36, 413\u2013432 (1999)","journal-title":"Bull. Am. Math. Soc"},{"doi-asserted-by":"crossref","unstructured":"Arthur, D.: Fast sorting and pattern-avoiding permutations. In: Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2007, pp. 169\u2013174 (2007)","key":"812_CR8","DOI":"10.1137\/1.9781611972979.1"},{"doi-asserted-by":"crossref","unstructured":"Ben-Eliezer, O., Canonne, C.L.: Improved bounds for testing forbidden order patterns. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 2093\u20132112 (2018)","key":"812_CR9","DOI":"10.1137\/1.9781611975031.137"},{"unstructured":"Berendsohn, B.A.: Complexity of permutation pattern matching. Master\u2019s thesis, Freie Universit\u00e4t Berlin, (2019)","key":"812_CR10"},{"unstructured":"Berndt, D.J., Clifford, J.: Using dynamic time warping to find patterns in time series. In: Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. AAAIWS\u201994, pp. 359\u2013370. AAAI Press, (1994)","key":"812_CR11"},{"issue":"1","key":"812_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"812_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.37236\/1693","volume":"9","author":"M B\u00f3na","year":"2003","unstructured":"B\u00f3na, M.: A survey of stack-sorting disciplines. Electron. J. Comb. 9(2), 1 (2003)","journal-title":"Electron. J. Comb."},{"key":"812_CR14","doi-asserted-by":"publisher","DOI":"10.1201\/9780203494370","volume-title":"Combinatorics of Permutations","author":"M B\u00f3na","year":"2004","unstructured":"B\u00f3na, M.: Combinatorics of Permutations. CRC Press Inc, Boca Raton, FL, USA (2004)"},{"key":"812_CR15","doi-asserted-by":"publisher","DOI":"10.1142\/8027","volume-title":"A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory","author":"M B\u00f3na","year":"2011","unstructured":"B\u00f3na, M.: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific, Singapore (2011)"},{"issue":"5","key":"812_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"Pt Bose","year":"1998","unstructured":"Bose, Pt, Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998)","journal-title":"Inf. Process. Lett."},{"unstructured":"Bringmann, K., Kozma, L., Moran, S., Narayanaswamy, N.S.: Hitting set for hypergraphs of low vc-dimension. In: 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, pp. 23:1\u201323:18, Aarhus, Denmark (2016)","key":"812_CR17"},{"issue":"2","key":"812_CR18","first-page":"83","volume":"24","author":"M-L Bruner","year":"2013","unstructured":"Bruner, M.-L., Lackner, M.: The computational landscape of permutation patterns. Pure Math. Appl. 24(2), 83\u2013101 (2013)","journal-title":"Pure Math. Appl."},{"issue":"1","key":"812_CR19","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/s00453-015-0013-y","volume":"75","author":"M-L Bruner","year":"2016","unstructured":"Bruner, M.-L., Lackner, M.: A fast algorithm for permutation pattern matching based on alternating runs. Algorithmica 75(1), 84\u2013117 (2016)","journal-title":"Algorithmica"},{"key":"812_CR20","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-319-94667-2_9","volume-title":"Combinatorial Algorithms","author":"L Bulteau","year":"2018","unstructured":"Bulteau, L., Rizzi, R., Vialette, S.: Pattern matching for k-track permutations. In: Iliopoulos, C., Leong, H.W., Sung, W.-K. (eds.) Combinatorial Algorithms, pp. 102\u2013114. Springer International Publishing, Cham (2018)"},{"doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K., Saranurak, T.: Pattern-avoiding access in binary search trees. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp. 410\u2013423, 2015","key":"812_CR21","DOI":"10.1109\/FOCS.2015.32"},{"issue":"6","key":"812_CR22","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0020-0190(92)90114-B","volume":"43","author":"M-S Chang","year":"1992","unstructured":"Chang, M.-S., Wang, F.-H.: Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs. Inf. Process. Lett. 43(6), 293\u2013295 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"812_CR23","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/1592451.1592453","volume":"42","author":"Hubie Chen","year":"2009","unstructured":"Chen, Hubie: A rendezvous of logic, complexity, and algebra. ACM Comput. Surv. 42(1), 2:1\u20132:32 (2009)","journal-title":"ACM Comput. Surv."},{"unstructured":"Cygan, M., Kowalik, L., Socala, A.: Improving TSP tours using dynamic programming over tree decompositions. In: 25th Annual European Symposium on Algorithms, ESA 2017, pp. 30:1\u201330:14, (2017)","key":"812_CR24"},{"issue":"3","key":"812_CR25","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38(3), 353\u2013366 (1989)","journal-title":"Artif. Intell."},{"unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity Monographs in Computer Science. Springer, Berlin(999)","key":"812_CR26"},{"issue":"2","key":"812_CR27","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1137\/16M1062879","volume":"31","author":"V Dujmovic","year":"2017","unstructured":"Dujmovic, V., Eppstein, D., Wood, D.R.: Structure of graphs with locally restricted crossings. SIAM J. Discrete Math. 31(2), 805\u2013824 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"812_CR28","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"issue":"2","key":"812_CR29","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"812_CR30","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., H\u00f8ie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5), 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"unstructured":"Fox, J.: Stanley-wilf limits are typically exponential. CoRR, arxiv: abs\/1310.8378, 2013","key":"812_CR31"},{"doi-asserted-by":"crossref","unstructured":"Fox, J., Wei, F.: Fast property testing and metrics for permutations. Combinatorics, Probability and Computing, pp. 1\u201341 (2018)","key":"812_CR32","DOI":"10.1017\/S096354831800024X"},{"unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Proceedings of the Eighth National Conference on Artificial Intelligence - Volume 1, AAAI\u201990, pp 4\u20139. AAAI Press, (1990)","key":"812_CR33"},{"doi-asserted-by":"crossref","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 82\u2013101 (2014)","key":"812_CR34","DOI":"10.1137\/1.9781611973402.7"},{"key":"812_CR35","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1007\/978-3-642-10631-6_107","volume-title":"Algorithms and Computation","author":"S Guillemot","year":"2009","unstructured":"Guillemot, S., Vialette, S.: Pattern matching for 321-avoiding permutations. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) Algorithms and Computation, pp. 1064\u20131073. Springer, Berlin Heidelberg (2009)"},{"issue":"1\u20133","key":"812_CR36","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"68","author":"K Hoffmann","year":"1986","unstructured":"Hoffmann, K., Mehlhorn, K., Rosenstiehl, P., Tarjan, R.E.: Sorting jordan sequences in linear time using level-linked search trees. Inf. Control 68(1\u20133), 170\u2013184 (1986)","journal-title":"Inf. Control"},{"issue":"6","key":"812_CR37","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(97)00029-X","volume":"61","author":"L Ibarra","year":"1997","unstructured":"Ibarra, L.: Finding pattern matchings for permutations. Inf. Process. Lett. 61(6), 293\u2013295 (1997)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Kyncl, J.: Hardness of permutation pattern matching. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 378\u2013396 (2017)","key":"812_CR38","DOI":"10.1137\/1.9781611974782.24"},{"doi-asserted-by":"crossref","unstructured":"Keogh, E.J., Lonardi, S., Yuan-chi Chiu, B.: Finding surprising patterns in a time series database in linear time and space. In: Proceedings of the Eighth ACM SIGKDD 2002 International Conference on Knowledge Discovery and Data Mining, pp. 550\u2013556, (2002)","key":"812_CR39","DOI":"10.1145\/775047.775128"},{"key":"812_CR40","volume-title":"Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series","author":"S Kitaev","year":"2011","unstructured":"Kitaev, S.: Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2011)"},{"key":"812_CR41","volume-title":"The Art of Computer Programming, Volume I: Fundamental Algorithms","author":"DE Knuth","year":"1968","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley, Boston (1968)"},{"issue":"129","key":"812_CR42","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1090\/S0025-5718-1975-0373371-6","volume":"29","author":"Donald E Knuth","year":"1975","unstructured":"Knuth, Donald E.: Estimating the efficiency of backtrack programs. Math. Comput. 29(129), 122\u2013136 (1975)","journal-title":"Math. Comput."},{"unstructured":"Knuth, D.E.: Dancing links. arXiv preprint cs\/0011047, (2000)","key":"812_CR43"},{"issue":"1","key":"812_CR44","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.jcta.2004.04.002","volume":"107","author":"A Marcus","year":"2004","unstructured":"Marcus, A., Tardos, G.: Excluded permutation matrices and the stanley-wilf conjecture. J. Comb. Theory Ser. A 107(1), 153\u2013160 (2004)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1","key":"812_CR45","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."},{"doi-asserted-by":"crossref","unstructured":"Neou, B., Rizzi, R., Vialette, S.: Permutation Pattern matching in (213, 231)-avoiding permutations. Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 2, Permutation Patterns 2015, March 2017","key":"812_CR46","DOI":"10.46298\/dmtcs.1329"},{"doi-asserted-by":"crossref","unstructured":"Newman, I., Rabinovich, Y., Rajendraprasad, D., Sohler, C.: Testing for forbidden order patterns in an array. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 1582\u20131597 (2017)","key":"812_CR47","DOI":"10.1137\/1.9781611974782.104"},{"key":"812_CR48","volume-title":"Combinatorial Algorithms","author":"A Nijenhuis","year":"1978","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms, 2nd edn. Academic Press Inc., Harcourt Brace Jovanovich, New York-London (1978)","edition":"2"},{"unstructured":"Patel, P., Keogh, E., Lin, J., Lonardi, S.: Mining motifs in massive time series databases. In: In Proceedings of IEEE International Conference on Data Mining ICDM\u201902, pp. 370\u2013377, (2002)","key":"812_CR49"},{"doi-asserted-by":"crossref","unstructured":"Pratt, V.R.: Computing permutations with double-ended queues, parallel stacks and parallel queues. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC \u201973, pp 268\u2013277. ACM, (1973)","key":"812_CR50","DOI":"10.1145\/800125.804058"},{"key":"812_CR51","first-page":"259","volume-title":"Graph Theory and Combinatorics","author":"P Rosenstiehl","year":"1984","unstructured":"Rosenstiehl, P.: Planar permutations defined by two intersecting Jordan curves. In: Bollob\u00e1s, B., Erd\u0151s, P. (eds.) Graph Theory and Combinatorics, pp. 259\u2013271. Academic Press, London (1984)"},{"issue":"3","key":"812_CR52","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0196-6774(84)90018-X","volume":"5","author":"P Rosenstiehl","year":"1984","unstructured":"Rosenstiehl, P., Tarjan, R.E.: Gauss codes, planar hamiltonian graphs, and stack-sortable permutations. J. Algorithms 5(3), 375\u2013390 (1984)","journal-title":"J. Algorithms"},{"unstructured":"Seidel, R.: A new method for solving constraint satisfaction problems. In: Proceedings of the 7th International Joint Conference on Artificial Intelligence, IJCAI 1981, pp. 338\u2013342, (1981)","key":"812_CR53"},{"issue":"4","key":"812_CR54","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/S0195-6698(85)80052-4","volume":"6","author":"R Simion","year":"1985","unstructured":"Simion, R., Schmidt, F.W.: Restricted permutations. Eur. J. Comb. 6(4), 383\u2013406 (1985)","journal-title":"Eur. J. Comb."},{"unstructured":"Sloane, N.J.A.: The encyclopedia of integer sequences, http:\/\/oeis.org. Sequence A073028","key":"812_CR55"},{"issue":"1","key":"812_CR56","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0012-365X(74)90073-9","volume":"9","author":"SM Tanny","year":"1974","unstructured":"Tanny, S.M., Zuker, M.: On a unimodal sequence of binomial coefficients. Discrete Math. 9(1), 79\u201389 (1974)","journal-title":"Discrete Math."},{"issue":"2","key":"812_CR57","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Sorting using networks of queues and stacks. J. ACM 19(2), 341\u2013346 (1972)","journal-title":"J. ACM"},{"key":"812_CR58","volume-title":"Foundations of Constraint Satisfaction. Computation in Cognitive Science","author":"EPK Tsang","year":"1993","unstructured":"Tsang, E.P.K.: Foundations of Constraint Satisfaction. Computation in Cognitive Science. Academic Press, Cambridge (1993)"},{"unstructured":"Vatter, V.: Permutation classes. In Mikl\u00f3s B\u00f3na, editor, Handbook of Enumerative Combinatorics, chapter\u00a012. Chapman and Hall\/CRC, New York, 2015. Preprint at arxiv: abs\/1409.5159","key":"812_CR59"},{"issue":"3","key":"812_CR60","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.dam.2004.10.004","volume":"146","author":"V Yugandhar","year":"2005","unstructured":"Yugandhar, V.: Saxena, Sanjeev: Parallel algorithms for separable permutations. Discrete Appl. Math. 146(3), 343\u2013364 (2005)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00812-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00812-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00812-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T09:48:51Z","timestamp":1671443331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00812-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,1]]},"references-count":60,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["812"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00812-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,3,1]]},"assertion":[{"value":"30 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}