{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T20:46:58Z","timestamp":1771102018699,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,3]],"date-time":"2014-05-03T00:00:00Z","timestamp":1399075200000},"content-version":"tdm","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":[[2015,8]]},"DOI":"10.1007\/s00453-014-9883-7","type":"journal-article","created":{"date-parts":[[2014,5,2]],"date-time":"2014-05-02T19:10:25Z","timestamp":1399057825000},"page":"940-968","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP"],"prefix":"10.1007","volume":"72","author":[{"given":"Keith","family":"Edwards","sequence":"first","affiliation":[]},{"given":"Eric","family":"McDermid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,3]]},"reference":[{"key":"9883_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","volume":"80","author":"S Arnborg","year":"1990","unstructured":"Arnborg, S., Proskurowski, A., Corneil, D.G.: Forbidden minors characterization of partial 3-trees. Discret. Math. 80, 1\u201319 (1990)","journal-title":"Discret. Math."},{"key":"9883_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Raman, V.: Upper bounds for MAXSAT: further improved, in Algorithms and computation Chennai. Lecture Notes in Computer Science, vol. 1741, pp. 247\u2013258. Springer, Berlin (1999)","DOI":"10.1007\/3-540-46632-0_26"},{"key":"9883_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$ k -arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9883_CR4","doi-asserted-by":"crossref","unstructured":"Cheng, C., McDermid, E., Suzuki, I.: Planarization and acyclic colorings of subcubic claw-free graphs. In: Kolman, P., Kratochv\u00edl, J. (eds.) Graph-Theoretic Concepts in Computer Science, WG 2011 (Czech Republic, June 2011). Lecture Notes in Computer Science, vol. 6986, pp. 107\u2013118. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25870-1_11"},{"key":"9883_CR5","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Ossona de Mendez, P.: A characterization of DFS cotree critical graphs. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) Graph Drawing 2001 (Vienna, 23\u201326 Sept. 2001), Lecture Notes in Computer Science, vol. 2265, pp. 84\u201395. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45848-4_7"},{"key":"9883_CR6","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/j.orl.2006.04.001","volume":"35","author":"F Della Croce","year":"2007","unstructured":"Della Croce, F., Kaminski, M.J., Paschos, V.T.H.: An exact algorithm for MAX-CUT in sparse graphs. Oper. Res. Lett. 35, 403\u2013408 (2007)","journal-title":"Oper. Res. Lett."},{"key":"9883_CR7","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1006\/jctb.2000.2018","volume":"82","author":"KJ Edwards","year":"2001","unstructured":"Edwards, K.J., Farr, G.F.: Fragmentability of graphs. J. Combin. Theory 82, 30\u201337 (2001)","journal-title":"J. Combin. Theory"},{"issue":"2","key":"9883_CR8","doi-asserted-by":"crossref","first-page":"#P25","DOI":"10.37236\/2378","volume":"19","author":"KJ Edwards","year":"2010","unstructured":"Edwards, K.J., Farr, G.E.: Improved upper bounds for planarization and series-parallelization of average degree bounded graphs. Electron. J. Comb. 19(2), #P25 (2010)","journal-title":"Electron. J. Comb."},{"key":"9883_CR9","unstructured":"Edwards, K.J., Farr, G.E.: Graph fragmentability. In: Beineke, L.W., Wilson, R.J. (eds.) Topics in Structural Graph Theory, Encyclopedia of Mathematics and its Applications No. 147, pp. 203\u2013218, Cambridge University Press, Cambridge (2013). ISBN 978-0-521-80231-4"},{"key":"9883_CR10","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54, 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"9883_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56, 1\u201332 (2009)","journal-title":"J. ACM"},{"key":"9883_CR12","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., H\u00f8ie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97, 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9883_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Texts in Theoretical Computer Science (2010). ISBN 978-3-642-16533-7","DOI":"10.1007\/978-3-642-16533-7"},{"key":"9883_CR14","unstructured":"Gaspers, S.: Exponential Time Algorithms: Structures, Measures, and Bounds. VDM Verlag Dr. Mueller e.K., 2010. ISBN 978-3-639-21825-1"},{"key":"9883_CR15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.jcss.2011.05.010","volume":"78","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Sorkin, G.B.: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. J. Comput. Syst. Sci. 78, 305\u2013335 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9883_CR16","doi-asserted-by":"crossref","unstructured":"Golovnev, A.: New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree. In: Parameterized and exact computation, Lecture Notes in Computer Science, vol. 7112, pp. 106\u2013117. Springer, Heidelberg (1973)","DOI":"10.1007\/978-3-642-28050-4_9"},{"key":"9883_CR17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.tcs.2014.01.010","volume":"526","author":"A Golovnev","year":"2014","unstructured":"Golovnev, A., Kutzkov, K.: New exact algorithms for the 2-constraint satisfaction problem. Theor. Comput. Sci. 526, 18\u201327 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9883_CR18","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J Gramm","year":"2003","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discret. Appl. Math. 130, 139\u2013155 (2003)","journal-title":"Discret. Appl. Math."},{"key":"9883_CR19","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/jgt.20271","volume":"57","author":"P Haxell","year":"2008","unstructured":"Haxell, P., Pikhurko, O., Thomason, A.: Maximum acyclic and fragmented sets in regular graphs. J. Graph Theory 57, 149\u2013156 (2008)","journal-title":"J. Graph Theory"},{"key":"9883_CR20","doi-asserted-by":"crossref","unstructured":"Hirsch, E.A.: A new algorithm for MAX-2-SAT, in: STACS 2000 (Lille), Lecture Notes in Computer Science, vol. 1770, pp. 65\u201373. Springer, Berlin (2000)","DOI":"10.1007\/3-540-46541-3_5"},{"key":"9883_CR21","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1137\/080715482","volume":"23","author":"J Kneis","year":"2009","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discret. Math. 23, 407\u2013427 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"9883_CR22","doi-asserted-by":"crossref","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms 2006, pp. 11\u201317. ACM, New York (2006)","DOI":"10.1145\/1109557.1109559"},{"key":"9883_CR23","doi-asserted-by":"crossref","unstructured":"Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning, in: Proceedings of the 2nd International Symposium on Computer Science in Russia (CSR 2007), Lecture Notes in Computer Science, vol. 4649, pp. 194\u2013204. Springer (2007)","DOI":"10.1007\/978-3-540-74510-5_21"},{"key":"9883_CR24","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms 36, 63\u201388 (2000)","journal-title":"J. Algorithms"},{"key":"9883_CR25","doi-asserted-by":"crossref","unstructured":"Raible, D., Fernau, H.: A new upper bound for Max-2-SAT: a graph-theoretic approach. In: Mathematical foundations of computer science 2008, Lecture Notes in Computer Science, vol. 5162, pp. 551\u2013562. Springer, Berlin, (2008)","DOI":"10.1007\/978-3-540-85238-4_45"},{"key":"9883_CR26","unstructured":"Robson, J.M.: Finding a maximum independent set in time $$O(2^{n\/4})$$ O ( 2 n \/ 4 ) . Technical Report 1251\u201301, LaBRI, Universit\u00e9 Bordeaux I (2001)"},{"key":"9883_CR27","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.disopt.2007.08.001","volume":"4","author":"AD Scott","year":"2007","unstructured":"Scott, A.D., Sorkin, G.B.: Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discret. Optim. 4, 260\u2013287 (2007)","journal-title":"Discret. Optim."},{"key":"9883_CR28","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1145\/1597036.1597049","volume":"5","author":"AD Scott","year":"2009","unstructured":"Scott, A.D., Sorkin, G.B.: Polynomial constraint satisfaction problems, graph bisection, and the Ising partition functio. ACM Trans. Algorithms 5, 45 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"9883_CR29","doi-asserted-by":"crossref","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: J. D\u00edaz et al. (eds.), Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP) (Turku, Finland, 2004), Lecture Notes in Computer Science, vol. 3142, pp. 1227\u20131237. Springer (2004)","DOI":"10.1007\/978-3-540-27836-8_101"},{"key":"9883_CR30","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial optimization\u2013Eureka, you shrink!, Lecture Notes in Computer Science vol. 2570, pp. 185\u2013207. Springer (2003)","DOI":"10.1007\/3-540-36478-1_17"},{"key":"9883_CR31","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/j.dam.2007.03.023","volume":"156","author":"GJ Woeginger","year":"2008","unstructured":"Woeginger, G.J.: Open problems around exact algorithms. Discret. Appl. Math. 156, 397\u2013405 (2008)","journal-title":"Discret. Appl. Math."},{"key":"9883_CR32","doi-asserted-by":"crossref","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. In: L. Cai, S.-W. Cheng, and T.-W. Lam (eds.), ISAAC2013, Lecture Notes in Computer Science, vol. 8283, pp. 328\u2013338. Springer (2013)","DOI":"10.1007\/978-3-642-45030-3_31"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9883-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9883-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9883-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,18]],"date-time":"2020-08-18T19:35:06Z","timestamp":1597779306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9883-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,3]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9883"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9883-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,3]]}}}