{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T15:50:03Z","timestamp":1725983403735},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319946665"},{"type":"electronic","value":"9783319946672"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94667-2_9","type":"book-chapter","created":{"date-parts":[[2018,7,3]],"date-time":"2018-07-03T07:56:24Z","timestamp":1530604584000},"page":"102-114","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Pattern Matching for k-Track Permutations"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,4]]},"reference":[{"issue":"2","key":"9_CR1","first-page":"629","volume":"22","author":"S Ahal","year":"2008","unstructured":"Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM JDM 22(2), 629\u2013649 (2008)","journal-title":"SIAM JDM"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-45678-3_31","volume-title":"Algorithms and Computation","author":"MH Albert","year":"2001","unstructured":"Albert, M.H., Aldred, R.E.L., Atkinson, M.D., Holton, D.A.: Algorithms for pattern involvement in permutations. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 355\u2013367. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45678-3_31"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Albert, M.H., Lackner, M.-L., Lackner, M., Vatter, V.: The complexity of pattern matching for 321-avoiding and skew-merged permutations. DMTCS 18(2) (2016)","DOI":"10.46298\/dmtcs.1308"},{"key":"9_CR4","first-page":"263","volume":"5","author":"MD Atkinson","year":"1998","unstructured":"Atkinson, M.D.: Permutations which are the union of an increasing and a decreasing. EJC 5, 263\u2013273 (1998)","journal-title":"EJC"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1090\/S0894-0347-99-00307-0","volume":"12","author":"J Baik","year":"1999","unstructured":"Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12, 1119\u20131178 (1999)","journal-title":"J. Amer. Math. Soc."},{"issue":"5","key":"9_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. IIPL 65(5), 277\u2013283 (1998)","journal-title":"IIPL"},{"key":"9_CR7","first-page":"263","volume":"22","author":"A Brandst\u00e4dt","year":"1986","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On partitions of permutations into increasing and decreasing subsequences. Elektron. Inf. Verarb. Kybern. EIK 22, 263\u2013273 (1986)","journal-title":"Elektron. Inf. Verarb. Kybern. EIK"},{"key":"9_CR8","unstructured":"Bruner, M.-L., Lackner, M.: The computational landscape of permutation patterns. CoRR, abs\/1301.0340 (2013)"},{"issue":"1","key":"9_CR9","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"},{"issue":"9","key":"9_CR10","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ic.2010.04.003","volume":"208","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inf. Comput. 208(9), 1054\u20131059 (2010)","journal-title":"Inf. Comput."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0020-0190(02)00288-0","volume":"84","author":"F Fomin","year":"2002","unstructured":"Fomin, F., Kratsch, D., Novelli, J.-C.: Approximating minimum cocolourings. IPL 84, 285\u2013290 (2002)","journal-title":"IPL"},{"key":"9_CR12","first-page":"82","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Sylvain Guillemot","year":"2013","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Chekuri, C. (ed.) SODA, pp. 82\u2013101. SIAM (2014)"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","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.) ISAAC 2009. LNCS, vol. 5878, pp. 1064\u20131073. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_107"},{"issue":"6","key":"9_CR14","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. IPL 61(6), 293\u2013295 (1997)","journal-title":"IPL"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/S0097-3165(96)80012-4","volume":"73","author":"AE K\u00e9zdy","year":"1996","unstructured":"K\u00e9zdy, A.E.: Partitioning permutations into increasing and decreasing subsequences. J. Comb. Theor. A 73(2), 353\u2013359 (1996)","journal-title":"J. Comb. Theor. A"},{"key":"9_CR16","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17333-2","volume-title":"Patterns in Permutations and Words","author":"S Kitaev","year":"2011","unstructured":"Kitaev, S.: Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-17333-2"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Kync\u0306l, J.: Hardness of permutation pattern matching. In: Klein, P. (ed.) SODA, pp. 378\u2013396. SIAM (2017)","DOI":"10.1137\/1.9781611974782.24"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-319-46049-9_25","volume-title":"String Processing and Information Retrieval","author":"BE Neou","year":"2016","unstructured":"Neou, B.E., Rizzi, R., Vialette, S.: Pattern matching for separable permutations. In: Inenaga, S., Sadakane, K., Sakai, T. (eds.) SPIRE 2016. LNCS, vol. 9954, pp. 260\u2013272. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-46049-9_25"},{"key":"9_CR19","series-title":"Computer Science and Applied Mathematics","volume-title":"Combinatorial Algorithms for Computers and Calculators","author":"A Nijenhuis","year":"1978","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms for Computers and Calculators. Computer Science and Applied Mathematics, 2nd edn. Academic Press, New York (1978)","edition":"2"},{"key":"9_CR20","series-title":"Institute of Mathematical Statistics Textbooks","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139872003","volume-title":"The Surprising Mathematics of Longest Increasing Subsequences","author":"D Romik","year":"2015","unstructured":"Romik, D.: The Surprising Mathematics of Longest Increasing Subsequences. Institute of Mathematical Statistics Textbooks, vol. 04. Cambridge University Press, Cambridge (2015)"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-1-4612-0801-3_9","volume":"72","author":"JM Steele","year":"1995","unstructured":"Steele, J.M.: Variations on the monotone subsequence theme of Erd\u00f6s and Szekeres. Discrete Probab. Algorithms 72, 111\u2013131 (1995)","journal-title":"Discrete Probab. Algorithms"},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/j.jda.2008.01.002","volume":"6","author":"G Stefano Di","year":"2008","unstructured":"Di Stefano, G., Krause, S., L\u00fcbbecke, M.E., Zimmermann, U.T.: On minimum k-modal partitions of permutations. JDA 6(3), 381\u2013392 (2008). https:\/\/doi.org\/10.1016\/j.jda.2008.01.002","journal-title":"JDA"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/11682462_36","volume-title":"LATIN 2006: Theoretical Informatics","author":"G Stefano Di","year":"2006","unstructured":"Di Stefano, G., Krause, S., L\u00fcbbecke, M.E., Zimmermann, U.T.: On minimum k-modal partitions of permutations. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 374\u2013385. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11682462_36"},{"issue":"12","key":"9_CR24","first-page":"633","volume":"20","author":"K Wagner","year":"1984","unstructured":"Wagner, K.: Monotonic coverings of finite sets. Elektronische Informationsverarbeitung und Kybernetik 20(12), 633\u2013639 (1984)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94667-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T22:02:14Z","timestamp":1661551334000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-94667-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319946665","9783319946672"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94667-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}