{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:26Z","timestamp":1740109286193,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T00:00:00Z","timestamp":1533859200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0497-3","type":"journal-article","created":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T09:09:38Z","timestamp":1533892178000},"page":"1684-1698","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Algorithms and Kernels for Rainbow Matching"],"prefix":"10.1007","volume":"81","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3633-542X","authenticated-orcid":false,"given":"Sanjukta","family":"Roy","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,10]]},"reference":[{"key":"497_CR1","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","volume":"110","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: An improved kernelization algorithm for r-set packing. Inf. Process. Lett. 110, 621\u2013624 (2010)","journal-title":"Inf. Process. Lett."},{"key":"497_CR2","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jcss.2017.03.003","volume":"87","author":"A Bj\u00f6rklund","year":"2017","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. 87, 119\u2013139 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"497_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"497_CR4","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: SODA\u201912 (2012)","DOI":"10.1137\/1.9781611973099.6"},{"key":"497_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"issue":"3","key":"497_CR6","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"5","key":"497_CR7","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1\u201325:32 (2009)","journal-title":"J. ACM"},{"key":"497_CR8","series-title":"An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010)"},{"key":"497_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, London (1979)"},{"key":"497_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An \n                    \n                      \n                    \n                    $$n^{5\/2}$$\n                    \n                      \n                        \n                          n\n                          \n                            5\n                            \/\n                            2\n                          \n                        \n                      \n                    \n                   algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"497_CR11","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/322092.322100","volume":"25","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M., Tanimoto, S.L.: Some matching problems for bipartite graphs. J. ACM 25(4), 517\u2013525 (1978)","journal-title":"J. ACM"},{"issue":"4","key":"497_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00373-008-0789-5","volume":"24","author":"M Kano","year":"2008","unstructured":"Kano, M., Li, X.: Monochromatic and heterochromatic subgraphs in edge-colored graphs\u2014a survey. Graphs Comb. 24(4), 237\u2013263 (2008)","journal-title":"Graphs Comb."},{"key":"497_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2013.12.013","volume":"524","author":"VB Le","year":"2014","unstructured":"Le, V.B., Pfender, F.: Complexity results for rainbow matchings. Theor. Comput. Sci. 524, 27\u201333 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"497_CR14","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. American Mathematical Society, Providence (2009)"},{"key":"497_CR15","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An \n                    \n                      \n                    \n                    $$O(\\sqrt{|V|} |E|)$$\n                    \n                      \n                        \n                          O\n                          (\n                          \n                            \n                              |\n                              V\n                              |\n                            \n                          \n                          |\n                          E\n                          |\n                          )\n                        \n                      \n                    \n                   algorithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13\u201315 October 1980, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"497_CR16","unstructured":"Ryser, H.J.: Neuere probleme der kombinatorik. In: Vortr\u00e4ge \u00fcber Kombinatorik, pp. 69\u201391. Matematisches Forschungsinstitute, Oberwolfach (1967)"},{"issue":"1","key":"497_CR17","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"497_CR18","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"key":"497_CR19","doi-asserted-by":"crossref","unstructured":"Zehavi, M.: Mixing color coding-related techniques. In: Algorithms\u2014ESA 2015\u201423rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, Volume 9294 of Lecture Notes in Computer Science, pp. 1037\u20131049 (2015)","DOI":"10.1007\/978-3-662-48350-3_86"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0497-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0497-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0497-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T19:08:33Z","timestamp":1565377713000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0497-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,10]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["497"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0497-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,8,10]]},"assertion":[{"value":"21 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}