{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:29Z","timestamp":1740109289842,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T00:00:00Z","timestamp":1566172800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T00:00:00Z","timestamp":1566172800000},"content-version":"vor","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":[[2020,4]]},"DOI":"10.1007\/s00453-019-00618-0","type":"journal-article","created":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T12:02:39Z","timestamp":1566216159000},"page":"881-897","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quadratic Vertex Kernel for Rainbow Matching"],"prefix":"10.1007","volume":"82","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":[[2019,8,19]]},"reference":[{"issue":"1","key":"618_CR1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.37236\/208","volume":"16","author":"R Aharoni","year":"2009","unstructured":"Aharoni, R., Berger, E.: Rainbow matchings in $$ r $$-partite $$ r $$-graphs. Electron. J. Combin. 16(1), 119 (2009)","journal-title":"Electron. J. Combin."},{"key":"618_CR2","first-page":"3","volume":"1","author":"N Alon","year":"2011","unstructured":"Alon, N.: Multicolored matchings in hypergraphs. Mosc. J. Combin. Number Theory 1, 3\u201310 (2011)","journal-title":"Mosc. J. Combin. Number Theory"},{"key":"618_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":"618_CR4","doi-asserted-by":"crossref","unstructured":"Diemunsch, J., Ferrara, M., Moffatt, C., Pfender, F., Wenger, P.S.: Rainbow matchings of size$$\\backslash $$delta (g) in properly edge-colored graphs. arXiv preprint \narXiv:1108.2521\n\n (2011)","DOI":"10.37236\/2443"},{"key":"618_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":"618_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."},{"key":"618_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2018)"},{"issue":"1","key":"618_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.37236\/140","volume":"16","author":"S Fujita","year":"2009","unstructured":"Fujita, S., Kaneko, A., Schiermeyer, I., Suzuki, K.: A rainbow $$ k $$-matching in the complete graph with $$ r $$ colors. Electron. J. Combin. 16(1), 51 (2009)","journal-title":"Electron. J. Combin."},{"key":"618_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, San Francisco (1979)"},{"key":"618_CR10","unstructured":"Glebov, R., Sudakov, B., Szab\u00f3, T.: How many colors guarantee a rainbow matching? arXiv preprint \narXiv:1211.0793\n\n (2012)"},{"key":"618_CR11","doi-asserted-by":"publisher","first-page":"1684","DOI":"10.1007\/s00453-018-0497-3","volume":"81","author":"S Gupta","year":"2019","unstructured":"Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Parameterized algorithms and kernels for rainbow matching. Algorithmica 81, 1684\u20131698 (2019). \nhttps:\/\/doi.org\/10.1007\/s00453-018-0497-3","journal-title":"Algorithmica"},{"issue":"4","key":"618_CR12","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":"618_CR13","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-a survey. Graphs Combin. 24(4), 237\u2013263 (2008)","journal-title":"Graphs Combin."},{"issue":"1\u20132","key":"618_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1017\/S0963548311000605","volume":"21","author":"A Kostochka","year":"2012","unstructured":"Kostochka, A., Yancey, M.: Large rainbow matchings in edge-coloured graphs. Combin. Probab. Comput. 21(1\u20132), 255\u2013263 (2012)","journal-title":"Combin. Probab. Comput."},{"key":"618_CR15","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."},{"issue":"1","key":"618_CR16","doi-asserted-by":"crossref","first-page":"26","DOI":"10.37236\/475","volume":"17","author":"TD LeSaulnier","year":"2010","unstructured":"LeSaulnier, T.D., Stocker, C., Wenger, P.S., West, D.B.: Rainbow matching in edge-colored graphs. Electron. J. Combin. 17(1), 26 (2010)","journal-title":"Electron. J. Combin."},{"issue":"11","key":"618_CR17","doi-asserted-by":"publisher","first-page":"2119","DOI":"10.1016\/j.disc.2015.05.015","volume":"338","author":"A Lo","year":"2015","unstructured":"Lo, A.: Existences of rainbow matchings and rainbow matching covers. Discrete Math. 338(11), 2119\u20132124 (2015)","journal-title":"Discrete Math."},{"key":"618_CR18","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, vol. 367. American Mathematical Society, Providence (2009)"},{"key":"618_CR19","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{|V|} |E|)$$ algorithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, NY, USA, 13\u201315 Oct 1980, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"618_CR20","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1016\/j.aim.2018.05.036","volume":"333","author":"A Pokrovskiy","year":"2018","unstructured":"Pokrovskiy, A.: An approximate version of a conjecture of Aharoni and Berger. Adv. Math. 333, 1197\u20131241 (2018)","journal-title":"Adv. Math."},{"key":"618_CR21","unstructured":"Ryser, H.J.: Neuere probleme der kombinatorik. Vortr\u00e4ge \u00fcber Kombinatorik, Oberwolfach, pp. 69\u201391 (1967)"},{"issue":"1","key":"618_CR22","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":"1","key":"618_CR23","doi-asserted-by":"crossref","first-page":"162","DOI":"10.37236\/649","volume":"18","author":"G Wang","year":"2011","unstructured":"Wang, G.: Rainbow matchings in properly edge colored graphs. Electron. J. Combin. 18(1), 162 (2011)","journal-title":"Electron. J. Combin."},{"issue":"1","key":"618_CR24","doi-asserted-by":"publisher","first-page":"138","DOI":"10.37236\/862","volume":"15","author":"G Wang","year":"2008","unstructured":"Wang, G., Li, H.: Heterochromatic matchings in edge-colored graphs. Electron. J. Combin. 15(1), 138 (2008)","journal-title":"Electron. J. Combin."},{"issue":"3","key":"618_CR25","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00618-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00618-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00618-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T23:18:14Z","timestamp":1597706294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00618-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,19]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["618"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00618-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,8,19]]},"assertion":[{"value":"7 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}