{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T20:46:49Z","timestamp":1771102009155,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"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":["J. ACM"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>For more than 40 years, Branch &amp; Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call \u201cMeasure &amp; Conquer\u201d, as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size; this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis.<\/jats:p>\n          <jats:p>In order to show the potentialities of Measure &amp; Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis).<\/jats:p>\n          <jats:p>Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.<\/jats:p>","DOI":"10.1145\/1552285.1552286","type":"journal-article","created":{"date-parts":[[2009,8,24]],"date-time":"2009-08-24T14:08:31Z","timestamp":1251122911000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":185,"title":["A measure &amp; conquer approach for the analysis of exact algorithms"],"prefix":"10.1145","volume":"56","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"University of Rome Tor Vergata, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[{"name":"University Paul Verlaine - Metz, Metz, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-005-9006-x"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Beigel R.","year":"1999","unstructured":"Beigel , R. 1999 . Finding maximum independent sets in sparse and general graphs . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 856--857. Beigel, R. 1999. Finding maximum independent sets in sparse and general graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 856--857."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.06.008"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.41"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_60"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.03.002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1145-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00174-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized complexity. Monographs in Computer Science. Springer-Verlag Berlin Germany.  Downey R. G. and Fellows M. R. 1999. Parameterized complexity. Monographs in Computer Science. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_14_1","first-page":"83","article-title":"Pseudo Boolean functions and stability of graphs","volume":"19","author":"Ebenegger C.","year":"1984","unstructured":"Ebenegger , C. , Hammer , P. L. , and de Werra , D. 1984 . Pseudo Boolean functions and stability of graphs . Ann. Disc. Math. 19 , 83 -- 98 . Ebenegger, C., Hammer, P. L., and de Werra, D. 1984. Pseudo Boolean functions and stability of graphs. Ann. Disc. Math. 19, 83--98.","journal-title":"Ann. Disc. Math."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00064"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45078-8_27"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198515"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9152-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_16"},{"key":"e_1_2_1_20_1","first-page":"47","article-title":"Some new techniques in design and analysis of exact (exponential) algorithms","volume":"87","author":"Fomin F.","year":"2005","unstructured":"Fomin , F. , Grandoni , F. , and Kratsch , D. 2005 b. Some new techniques in design and analysis of exact (exponential) algorithms . Bull. Europ. Assoc. Theoret. Comput. Sci. 87 , 47 -- 77 . Fomin, F., Grandoni, F., and Kratsch, D. 2005b. Some new techniques in design and analysis of exact (exponential) algorithms. Bull. Europ. Assoc. Theoret. Comput. Sci. 87, 47--77.","journal-title":"Bull. Europ. Assoc. Theoret. Comput. Sci."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109560"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435384"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9145-z"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643350"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30559-0_21"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Computing and Combinatorics Conference (COCOON). 65--74","author":"Fomin F. V.","unstructured":"Fomin , F. V. , and Stepanov , A . 2007. Counting minimum weighted dominating sets . In Proceedings of the International Computing and Combinatorics Conference (COCOON). 65--74 . Fomin, F. V., and Stepanov, A. 2007. Counting minimum weighted dominating sets. In Proceedings of the International Computing and Combinatorics Conference (COCOON). 65--74."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_46"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_8"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00402-X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.03.002"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944836_15"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_34_1","unstructured":"Haynes T. W. Hedetniemi S. T. and Slater P. J. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc. New York.  Haynes T. W. Hedetniemi S. T. and Slater P. J. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc. New York."},{"key":"e_1_2_1_35_1","first-page":"196","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held M.","year":"1962","unstructured":"Held , M. , and Karp , R. M. 1962 . A dynamic programming approach to sequencing problems . J. SIAM 10 , 196 -- 210 . Held, M., and Karp, R. M. 1962. A dynamic programming approach to sequencing problems. J. SIAM 10, 196--210.","journal-title":"J. SIAM"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006340920104"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006318521185"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_40_1","first-page":"61","article-title":"Worst-case upper bounds for k-SAT","volume":"82","author":"Iwama K.","year":"2004","unstructured":"Iwama , K. 2004 . Worst-case upper bounds for k-SAT . Bull. Europ. Associ. Theoret. Comp. Sci. 82 , 61 -- 71 . Iwama, K. 2004. Worst-case upper bounds for k-SAT. Bull. Europ. Associ. Theoret. Comp. Sci. 82, 61--71.","journal-title":"Bull. Europ. Associ. Theoret. Comp. Sci."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Iwama K.","unstructured":"Iwama , K. , and Tamaki , S . 2004. Improved upper bounds for 3-SAT . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 328--329. Iwama, K., and Tamaki, S. 2004. Improved upper bounds for 3-SAT. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 328--329."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676847"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800179.810218"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.11"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109559"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_9"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.06.014"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00017-6"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90065-X"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90050-2"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066101"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) ACM","author":"Pudlak P.","unstructured":"Pudlak , P. , and Impagliazzo , R . 2000. A lower bound for DLL algorithms for k-SAT . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) ACM , New York, 128--136. Pudlak, P., and Impagliazzo, R. 2000. A lower bound for DLL algorithms for k-SAT. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) ACM, New York, 128--136."},{"key":"e_1_2_1_53_1","unstructured":"Randerath B. and Schiermeyer I. 2004. Exact algorithms for MINIMUM DOMINATING SET. Tech. Rep. zaik-469 Zentrum f&amp;#252;r Angewandte Informatik K&amp;#246;ln Germany.  Randerath B. and Schiermeyer I. 2004. Exact algorithms for MINIMUM DOMINATING SET. Tech. Rep. zaik-469 Zentrum f&amp;#252;r Angewandte Informatik K&amp;#246;ln Germany."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_17"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the Algorithms and Complexity in Durham Workshop (ACiD). 131--142","author":"Razgon I.","year":"2006","unstructured":"Razgon , I. 2006 b. A faster solving of the maximum independent set problem for graphs with maximal degree 3 . In Proceedings of the Algorithms and Complexity in Durham Workshop (ACiD). 131--142 . Razgon, I. 2006b. A faster solving of the maximum independent set problem for graphs with maximal degree 3. In Proceedings of the Algorithms and Complexity in Durham Workshop (ACiD). 131--142."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300002042"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.08.010"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_2_1_61_1","volume-title":"Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, 410--414","author":"Sch","year":"1999","unstructured":"Sch &amp;#246;ning, U. 1999 . A probabilistic algorithm for k-SAT and constraint satisfaction problems . In Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, 410--414 . Sch&amp;#246;ning, U. 1999. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, 410--414."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_3"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210033"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 657--668","author":"van Rooij J.","unstructured":"van Rooij , J. , and Bodlaender , H. L . 2008. Design by measure and conquer, a faster exact algorithm for dominating set . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 657--668 . van Rooij, J., and Bodlaender, H. L. 2008. Design by measure and conquer, a faster exact algorithm for dominating set. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 657--668."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_73"},{"key":"e_1_2_1_67_1","volume-title":"Introduction to Graph Theory","author":"West D. B.","unstructured":"West , D. B. 1996. Introduction to Graph Theory . Prentice Hall , Englewood Cliffs . West, D. B. 1996. Introduction to Graph Theory. Prentice Hall, Englewood Cliffs."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/885909.885927"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1552285.1552286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1552285.1552286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:04Z","timestamp":1750253404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1552285.1552286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":68,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1552285.1552286"],"URL":"https:\/\/doi.org\/10.1145\/1552285.1552286","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}