{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:18:42Z","timestamp":1759133922625,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>\n            For a graph\n            <jats:italic>G<\/jats:italic>\n            with real weights assigned to the vertices (edges), the MAX\n            <jats:italic>H<\/jats:italic>\n            -SUBGRAPH problem is to find an\n            <jats:italic>H<\/jats:italic>\n            -subgraph of\n            <jats:italic>G<\/jats:italic>\n            with maximum total weight, if one exists. Our main results are new strongly polynomial algorithms for the MAX\n            <jats:italic>H<\/jats:italic>\n            -SUBGRAPH problem. Some of our algorithms are based, in part, on fast matrix multiplication.\n          <\/jats:p>\n          <jats:p>\n            For vertex-weighted graphs with\n            <jats:italic>n<\/jats:italic>\n            vertices we solve a more general problem: the\n            <jats:italic>all pairs<\/jats:italic>\n            MAX\n            <jats:italic>H<\/jats:italic>\n            -SUBGRAPH problem, where the task is to find for every pair of vertices\n            <jats:italic>u,v,<\/jats:italic>\n            a maximum\n            <jats:italic>H<\/jats:italic>\n            -subgraph containing both\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            , if one exists. We obtain an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>t<\/jats:italic>\n              (\u03c9,\n              <jats:italic>h<\/jats:italic>\n              ))\n            <\/jats:sup>\n            -time algorithm for the\n            <jats:italic>all pairs<\/jats:italic>\n            MAX\n            <jats:italic>H<\/jats:italic>\n            -SUBGRAPH problem in the case where\n            <jats:italic>H<\/jats:italic>\n            is a fixed graph with\n            <jats:italic>h<\/jats:italic>\n            vertices and\n            <jats:italic>\u03c9<\/jats:italic>\n            &lt; 2.376 is the exponent of matrix multiplication. The value of\n            <jats:italic>t<\/jats:italic>\n            (\u03c9,\n            <jats:italic>h<\/jats:italic>\n            ) is determined by solving a small integer program. In particular, heaviest triangles for all pairs can be found in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2+1\/(4-\u03c9)<\/jats:sup>\n            ) \u2264\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.616<\/jats:sup>\n            )-time. For\n            <jats:italic>h<\/jats:italic>\n            =4,5,8 the running time of our algorithm essentially matches that of the (unweighted)\n            <jats:italic>H<\/jats:italic>\n            -subgraph detection problem. Using rectangular matrix multiplication, the value of\n            <jats:italic>t<\/jats:italic>\n            (\n            <jats:italic>\u03c9,h<\/jats:italic>\n            ) can be improved; for example, the runtime for triangles becomes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.575<\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>\n            We also present improved algorithms for the MAX\n            <jats:italic>H<\/jats:italic>\n            -SUBGRAPH problem in the edge-weighted case. In particular, we obtain an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              2\u22121\/\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm for the heaviest cycle of length 2\n            <jats:italic>k<\/jats:italic>\n            or 2\n            <jats:italic>k<\/jats:italic>\n            \u22121 in a graph with\n            <jats:italic>m<\/jats:italic>\n            edges and an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \/log\n            <jats:italic>n<\/jats:italic>\n            )-time randomized algorithm for finding the heaviest cycle of any fixed length.\n          <\/jats:p>\n          <jats:p>\n            Our methods also yield efficient algorithms for several related problems that are faster than any previously existing algorithms. For example, we show how to find chromatic\n            <jats:italic>H<\/jats:italic>\n            -subgraphs in edge-colored graphs, and how to compute the most significant bits of the distance product of two real matrices, in truly subcubic time.\n          <\/jats:p>","DOI":"10.1145\/1798596.1798597","type":"journal-article","created":{"date-parts":[[2010,6,29]],"date-time":"2010-06-29T13:02:22Z","timestamp":1277816542000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Finding heaviest\n            <i>H<\/i>\n            -subgraphs in real weighted graphs, with applications"],"prefix":"10.1145","volume":"6","author":[{"given":"Virginia","family":"Vassilevska","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940874"},{"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.1007\/BF02523189"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.08.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_28"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250877"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009552"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0438"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1014"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1385"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_38"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_24_1","unstructured":"Kerr L. R. 1970. The effect of algebraic structure on the computational complexity of matrix multiplications. Ph.D. thesis Cornell University Ithaca NY.   Kerr L. R. 1970. The effect of algebraic structure on the computational complexity of matrix multiplications. Ph.D. thesis Cornell University Ithaca NY."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00047-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_20"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90071-O"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100244"},{"key":"e_1_2_1_30_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Nesetril J.","year":"1985","journal-title":"Comment. Math. Univ. Carolin."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90041-7"},{"volume":"484","volume-title":"Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'91)","author":"Plehn J.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1078"},{"volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99)","author":"Shoshan A.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132550"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_24"},{"volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Yuster R.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90085-5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1798596.1798597","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1798596.1798597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:58Z","timestamp":1750245778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1798596.1798597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1798596.1798597"],"URL":"https:\/\/doi.org\/10.1145\/1798596.1798597","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}