{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:42:44Z","timestamp":1725856964644},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319398167"},{"type":"electronic","value":"9783319398174"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-39817-4_7","type":"book-chapter","created":{"date-parts":[[2016,5,26]],"date-time":"2016-05-26T09:15:09Z","timestamp":1464254109000},"page":"65-74","source":"Crossref","is-referenced-by-count":0,"title":["Improved Algorithms for Several Parameterized Problems Based on Random Methods"],"prefix":"10.1007","author":[{"given":"Qilong","family":"Feng","sequence":"first","affiliation":[]},{"given":"Xiong","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,27]]},"reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/j.jda.2006.09.001","volume":"5","author":"N Ahuja","year":"2007","unstructured":"Ahuja, N., Baltz, A., Doerr, B., Privtivy, A., Srivastav, A.: On the minimum load coloring problem. J. Discrete Algorithms 5(3), 533\u2013545 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"7_CR2","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 732\u2013741 (2002)"},{"key":"7_CR3","doi-asserted-by":"crossref","first-page":"1686","DOI":"10.1016\/j.dam.2011.11.008","volume":"161","author":"D Binkele-Raible","year":"2013","unstructured":"Binkele-Raible, D., Fernau, H.: Packing paths: recycling saves time. Discrete Appl. Math. 161, 1686\u20131689 (2013)","journal-title":"Discrete Appl. Math."},{"key":"7_CR4","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings (2010). CoRR abs\/1007.1161"},{"issue":"23","key":"7_CR5","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 412(23), 2503\u20132512 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"7_CR6","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/s00453-008-9206-y","volume":"54","author":"J Chen","year":"2008","unstructured":"Chen, J., Lu, S.: Improved parameterized set splitting algorithms: a probabilistic approach. Algorithmica 54(4), 472\u2013489 (2008)","journal-title":"Algorithmica"},{"key":"7_CR7","unstructured":"Chen, J., Lu, S., Sze, S.H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 298\u2013307 (2007)"},{"key":"7_CR8","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Leeuwen, E., Wrochna, E.: Polynomial kernelization for removing induced claws and diamonds (2015). arXiv preprint arXiv:1503.00704"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-540-30559-0_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Fellows","year":"2004","unstructured":"Fellows, M., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding k disjoint triangles in an arbitrary graph. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 235\u2013244. Springer, Heidelberg (2004)"},{"key":"7_CR10","unstructured":"Gabow, H.: Data structures for weighted matching and nearest common ancestoers. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434\u2013443 (1990)"},{"key":"7_CR11","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1016\/j.ipl.2014.03.008","volume":"114","author":"G Gutin","year":"2014","unstructured":"Gutin, G., Jones, M.: Parameterized algorithms for load coloring problem. Inf. Process. Lett. 114, 446\u2013449 (2014)","journal-title":"Inf. Process. Lett."},{"key":"7_CR12","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.dam.2005.11.003","volume":"154","author":"R Hassin","year":"2006","unstructured":"Hassin, R., Rubinstein, S.: An approximation algorithm for maximum triangle packing. Discrete Appl. Math. 154, 971\u2013979 (2006)","journal-title":"Discrete Appl. Math."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Hell, P., Kirkpatrick, D.: On the complexity of a generalized matching problem. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 240\u2013245 (1978)","DOI":"10.1145\/800133.804353"},{"key":"7_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C Hurkens","year":"1989","unstructured":"Hurkens, C., Schrijver, A.: On the size of systems of sets every $$t$$ of which have an SDR, with application to worst case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2, 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0020-0190(94)90105-8","volume":"49","author":"V Kann","year":"1994","unstructured":"Kann, V.: Maximum bounded $$H$$ -matching is MAX-SNP-complete. Inf. Process. Lett. 49, 309\u2013318 (1994)","journal-title":"Inf. Process. Lett."},{"key":"7_CR16","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"DG Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput. 12, 601\u2013609 (1983)","journal-title":"SIAM J. Comput."},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/978-3-642-33293-7_2","volume-title":"Parameterized and Exact Computation","author":"D Marx","year":"2012","unstructured":"Marx, D.: Randomized techniques for parameterized algorithms. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, p. 2. Springer, Heidelberg (2012)"},{"key":"7_CR19","unstructured":"Zehavi, M.: Deterministic parameterized algorithms for matching and packing problems (2013). arXiv:1311.0484v2"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-39817-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T18:24:12Z","timestamp":1567967052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-39817-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319398167","9783319398174"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-39817-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}