{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:25:54Z","timestamp":1747196754409,"version":"3.40.5"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_8","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"85-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The $$k$$-Distinct Language: Parameterized Automata Constructions"],"prefix":"10.1007","author":[{"given":"Ran","family":"Ben-Basat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"key":"8_CR1","first-page":"12","volume":"20","author":"H Abasi","year":"2013","unstructured":"Abasi, H., Bshouty, N.: A simple algorithm for undirected hamiltonicity. Electron. Colloquium Comput. Complex. (ECCC) 20, 12 (2013)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-11269-0_1","volume-title":"Parameterized and Exact Computation","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Balanced hashing, color coding and approximate counting. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 1\u201316. Springer, Heidelberg (2009)"},{"issue":"4","key":"8_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color coding. J. Assoc. Comput. Mach. 42(4), 844\u2013856 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"8_CR4","unstructured":"Ben-Basat, R.: M.Sc. thesis. Technical reports and theses, Technion (2015)"},{"key":"8_CR5","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161 (2010)"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993)","journal-title":"J. Algorithms"},{"issue":"23","key":"8_CR7","doi-asserted-by":"publisher","first-page":"2503","DOI":"10.1016\/j.tcs.2010.10.042","volume":"412","author":"J Chen","year":"2011","unstructured":"Chen, J., Feng, Q., Liu, Y., Lu, S., Wang, J.: Improved deterministic algorithms for weighted matching and packing problems. Theor. Comput. Sci. 412(23), 2503\u20132512 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00453-004-1096-z","volume":"40","author":"J Chen","year":"2004","unstructured":"Chen, J., Friesen, D., Jia, W., Kanj, I.: Using nondeterminism to design effcient deterministic algorithms. Algorithmica 40(2), 83\u201397 (2004)","journal-title":"Algorithmica"},{"issue":"6","key":"8_CR9","doi-asserted-by":"publisher","first-page":"2526","DOI":"10.1137\/080716475","volume":"38","author":"J Chen","year":"2009","unstructured":"Chen, J., Kneis, J., Lu, S., Molle, D., Richter, S., Rossmanith, P., Sze, S.H., Zhang, F.: Randomized divide-and-conquer: improved path, matching, and packing algorithms. SIAM J. Comput. 38(6), 2526\u20132547 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2071379.2071385","volume":"8","author":"J Chen","year":"2012","unstructured":"Chen, J., Liu, Y., Lu, S., Sze, S.H., Zhang, F.: Iterative expansion and color coding: an improved algorithm for 3D-matching. ACM Trans. Algorithms 8(1), 6 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"8_CR11","unstructured":"Chen, S., Chen, Z.: Faster deterministic algorithms for packing, matching and $$t$$-dominating set problems. CoRR abs\/1306.360 (2013)"},{"key":"8_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"8_CR13","unstructured":"Downey, R.G., Fellows, M.R., Koblitz, M.: Techniques for exponential parameterized reductions in vertex set problems (Unpublished, reported in [12], Sect. 8.3)"},{"issue":"2","key":"8_CR14","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s00453-007-9146-y","volume":"52","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F.A., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167\u2013176 (2008)","journal-title":"Algorithmica"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact agorithms. In: SODA, pp. 142\u2013151 (2014)","DOI":"10.1137\/1.9781611973402.10"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative sets of product families. In: ESA (2014, to appear)","DOI":"10.1007\/978-3-662-44777-2_37"},{"key":"8_CR17","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)"},{"key":"8_CR18","unstructured":"Goyal, P., Misra, N., Panolan, F.: Faster deterministic algorithms for $$r$$-dimensional matching using representative sets. In: FSTTCS, pp. 237\u2013248 (2013)"},{"key":"8_CR19","unstructured":"Goyal, P., Misra, N., Panolan, F., Zehavi, M.: Faster deterministic algorithms for matching and packing problems. Unpublished, results reported in [18, 40] (2014)"},{"key":"8_CR20","unstructured":"Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: LATA, pp. 261\u2013272 (2007)"},{"issue":"2","key":"8_CR21","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/s00453-007-9008-7","volume":"52","author":"F H\u00fcffner","year":"2008","unstructured":"H\u00fcffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica 52(2), 114\u2013132 (2008)","journal-title":"Algorithmica"},{"issue":"3","key":"8_CR22","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(73)90098-8","volume":"6","author":"DJ Kleitman","year":"1972","unstructured":"Kleitman, D.J., Spencer, J.: Families of k-independent sets. Discrete Math. 6(3), 255\u2013262 (1972)","journal-title":"Discrete Math."},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.ipl.2004.12.005","volume":"94","author":"I Koutis","year":"2005","unstructured":"Koutis, I.: A faster parameterized algorithm for set packing. Inf. Proc. Lett. 94, 7\u20139 (2005)","journal-title":"Inf. Proc. Lett."},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, Languages and Programming","author":"I Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 575\u2013586. Springer, Heidelberg (2008)"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-3-642-02927-1_54","volume-title":"Automata, Languages and Programming","author":"I Koutis","year":"2009","unstructured":"Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 653\u2013664. Springer, Heidelberg (2009)"},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"Liu, Y., Chen, J., Wang, J.: On efficient FPT algorithms for weighted matching and packing problems. In: TAMC, pp. 575\u2013586 (2007)","DOI":"10.1007\/978-3-540-72504-6_63"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-73545-8_35","volume-title":"Computing and Combinatorics","author":"Y Liu","year":"2007","unstructured":"Liu, Y., Chen, J., Wang, J.: A randomized approximation algorithm for parameterized 3-d matching counting problem. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 349\u2013359. Springer, Heidelberg (2007)"},{"key":"8_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/11847250_8","volume-title":"Parameterized and Exact Computation","author":"Y Liu","year":"2006","unstructured":"Liu, Y., Lu, S., Chen, J., Sze, S.-H.: Greedy localization and color-coding: improved matching and packing algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 84\u201395. Springer, Heidelberg (2006)"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"M. Naor, L.J.S., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"6","key":"8_CR30","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235\u20131258 (1995)","journal-title":"SIAM J. Comput."},{"key":"8_CR31","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discrete Math. 25, 239\u2013254 (1985)","journal-title":"Ann. Discrete Math."},{"key":"8_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-30642-6_26","volume-title":"Computer Science \u2013 Theory and Applications","author":"R Rizzi","year":"2012","unstructured":"Rizzi, R., Sikora, F.: Some results on more flexible versions of graph motif. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 278\u2013289. Springer, Heidelberg (2012)"},{"key":"8_CR33","series-title":"The Carus Mathematical Monographs","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440147","volume-title":"Combinatorial Mathematics","author":"HJ Ryser","year":"1963","unstructured":"Ryser, H.J.: Combinatorial Mathematics. The Carus Mathematical Monographs. The Mathematical Association of America, Washington (1963)"},{"issue":"3","key":"8_CR34","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1109\/18.6031","volume":"34","author":"G Seroussi","year":"1988","unstructured":"Seroussi, G., Bshouty, N.H.: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inf. Theory 34(3), 513\u2013522 (1988)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1007\/978-3-662-44777-2_65","volume-title":"Algorithms - ESA 2014","author":"H Shachnai","year":"2014","unstructured":"Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 786\u2013797. Springer, Heidelberg (2014)"},{"key":"8_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-02979-0_6","volume-title":"Implementation and Application of Automata","author":"J Vuillemin","year":"2009","unstructured":"Vuillemin, J., Gama, N.: Compact normal form for regular languages as xor automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 24\u201333. Springer, Heidelberg (2009)"},{"key":"8_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978-3-540-69733-6_14","volume-title":"Computing and Combinatorics","author":"J Wang","year":"2008","unstructured":"Wang, J., Feng, Q.: Improved parameterized algorithms for weighted 3-set packing. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 130\u2013139. Springer, Heidelberg (2008)"},{"key":"8_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-540-79228-4_7","volume-title":"Theory and Applications of Models of Computation","author":"J Wang","year":"2008","unstructured":"Wang, J., Feng, Q.: An $${\\rm {O}}^*(3.523^k)$$ parameterized algorithm for 3-set packing. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 82\u201393. Springer, Heidelberg (2008)"},{"issue":"6","key":"8_CR39","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $$k$$ in $${O}^*(2^k)$$ time. Inf. Proc. Let. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Proc. Let."},{"key":"8_CR40","unstructured":"Zehavi, M.: Deterministic parameterized algorithms for matching and packing problems. CoRR abs\/1311.0484 (2013)"},{"key":"8_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1007\/978-3-642-40313-2_72","volume-title":"Mathematical Foundations of Computer Science 2013","author":"M Zehavi","year":"2013","unstructured":"Zehavi, M.: Parameterized algorithms for module motif. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 825\u2013836. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:34:33Z","timestamp":1747175673000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}