{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:31Z","timestamp":1759638991088,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0430683CCF-0830455CCF-0311590"],"award-info":[{"award-number":["CCF-0430683CCF-0830455CCF-0311590"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            The research in the parameterized\n            <jats:sc>3d-matching<\/jats:sc>\n            problem has yielded a number of new algorithmic techniques and an impressive list of improved algorithms. In this article, a new deterministic algorithm for the problem is developed that integrates and improves a number of known techniques, including greedy localization, dynamic programming, and color coding. The new algorithm, which either constructs a matching of\n            <jats:italic>k<\/jats:italic>\n            triples in a given triple set or correctly reports that no such a matching exists, runs in time\n            <jats:italic>O<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (2.80\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ), improving a long list of previous algorithms for the problem.\n          <\/jats:p>","DOI":"10.1145\/2071379.2071385","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Iterative Expansion and Color Coding"],"prefix":"10.1145","volume":"8","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[{"name":"Texas A&amp;M University"}]},{"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Texas - Pan American"}]},{"given":"Songjian","family":"Lu","sequence":"additional","affiliation":[{"name":"Medical University of South Carolina"}]},{"given":"Sing-Hoi","family":"Sze","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University"}]},{"given":"Fenghui","family":"Zhang","sequence":"additional","affiliation":[{"name":"Google Inc."}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Gutner S. 2009. Balanced hashing color coding and approximate counting. Electronic Colloquium on Computational Complexity. Report No. 12. Alon N. and Gutner S. 2009. Balanced hashing color coding and approximate counting. Electronic Colloquium on Computational Complexity . Report No. 12.","DOI":"10.1007\/978-3-642-11269-0_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1096-z"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Chen J.","key":"e_1_2_1_5_1","unstructured":"Chen , J. , Lu , S. , Sze , S.-H. , and Zhang , F . 2007. Improved algorithms for path, matching, and packing problems . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . 298--307. Chen, J., Lu, S., Sze, S.-H., and Zhang, F. 2007. Improved algorithms for path, matching, and packing problems. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 298--307."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC\u201904)","volume":"3162","author":"Dehne F.","unstructured":"Dehne , F. , Fellows , M. , Rosamond , F. , and Shaw , P . 2004. Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, and improved algorithm for set splitting, and a novel 2k kernelization of vertex cover . In Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC\u201904) . Lecture Notes in Computer Science , vol. 3162 , Springer-Verlag, Berlin, 271--280. Dehne, F., Fellows, M., Rosamond, F., and Shaw, P. 2004. Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, and improved algorithm for set splitting, and a novel 2k kernelization of vertex cover. In Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC\u201904). Lecture Notes in Computer Science, vol. 3162, Springer-Verlag, Berlin, 271--280."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parameterized Complexity. Springer New York. Downey R. and Fellows M. 1999. Parameterized Complexity . Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9146-y"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_10_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co. New York. Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman & Co. New York."},{"key":"e_1_2_1_11_1","unstructured":"Hardy G. and Wright E. 1978. An Introduction to the Theory of Numbers 5th Ed. Oxford University Press Oxford UK. Hardy G. and Wright E. 1978. An Introduction to the Theory of Numbers 5th Ed. Oxford University Press Oxford UK."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.07.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.12.005"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 5th International Conference on Theory and Applications of Models of Compuitation (TAMC\u201908)","volume":"4978","author":"Wang J.","unstructured":"Wang , J. , and Feng , Q . 2008. An O *(3.523 k) parameterized algorithm for 3-set packing . In Proceedings of the 5th International Conference on Theory and Applications of Models of Compuitation (TAMC\u201908) . Lecture Notes in Computer Science , vol. 4978 , Springer-Verlag, Berlin, 82--93. Wang, J., and Feng, Q. 2008. An O *(3.523 k) parameterized algorithm for 3-set packing. In Proceedings of the 5th International Conference on Theory and Applications of Models of Compuitation (TAMC\u201908). Lecture Notes in Computer Science, vol. 4978, Springer-Verlag, Berlin, 82--93."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071385","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071379.2071385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071385"}},"subtitle":["An Improved Algorithm for 3D-Matching"],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071379.2071385"],"URL":"https:\/\/doi.org\/10.1145\/2071379.2071385","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}