{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:00:15Z","timestamp":1743084015832,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":23,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819628445"},{"type":"electronic","value":"9789819628452"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-2845-2_6","type":"book-chapter","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T15:59:59Z","timestamp":1740067199000},"page":"79-93","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Piecewise Approach for\u00a0the\u00a0Analysis of\u00a0Exact Algorithms"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2653-9576","authenticated-orcid":false,"given":"Katie","family":"Clinch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6947-9238","authenticated-orcid":false,"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1742-3937","authenticated-orcid":false,"given":"Zixu","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9805-8291","authenticated-orcid":false,"given":"Abdallah","family":"Saffidine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1493-7595","authenticated-orcid":false,"given":"Tiankuang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time $$O(1.3289)^n$$. J. Algorithms 54(2), 168\u2013204 (2005). https:\/\/doi.org\/10.1016\/j.jalgor.2004.06.008","DOI":"10.1016\/j.jalgor.2004.06.008"},{"key":"6_CR2","doi-asserted-by":"publisher","unstructured":"Clinch, K., Gaspers, S., Saffidine, A., He, Z., Zhang, T.: A piecewise approach for the analysis of exact algorithms. CoRR abs\/2402.10015 (2024). https:\/\/doi.org\/10.48550\/arXiv.2402.10015","DOI":"10.48550\/arXiv.2402.10015"},{"issue":"4","key":"6_CR3","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1007\/s00453-014-9883-7","volume":"72","author":"K Edwards","year":"2015","unstructured":"Edwards, K., McDermid, E.: A general reduction theorem with applications to pathwidth and the complexity of MAX 2-CSP. Algorithmica 72(4), 940\u2013968 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9883-7","journal-title":"Algorithmica"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-44634-6_42","volume-title":"Algorithms and Data Structures","author":"D Eppstein","year":"2001","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 462\u2013470. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44634-6_42"},{"issue":"4","key":"6_CR5","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1145\/1198513.1198515","volume":"2","author":"D Eppstein","year":"2006","unstructured":"Eppstein, D.: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans. Algorithms 2(4), 492\u2013509 (2006). https:\/\/doi.org\/10.1145\/1198513.1198515","journal-title":"ACM Trans. Algorithms"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-540-73545-8_9","volume-title":"Computing and Combinatorics","author":"FV Fomin","year":"2007","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Improved exact algorithms for counting 3- and 4-colorings. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 65\u201374. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73545-8_9"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","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(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"6_CR8","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/S00453-010-9418-9","volume":"61","author":"FV Fomin","year":"2011","unstructured":"Fomin, F.V., Golovach, P.A., Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Branch and recharge: Exact algorithms for generalized domination. Algorithmica 61(2), 252\u2013273 (2011). https:\/\/doi.org\/10.1007\/S00453-010-9418-9","journal-title":"Algorithmica"},{"key":"6_CR9","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1\u201325:32 (2009). https:\/\/doi.org\/10.1145\/1552285.1552286","DOI":"10.1145\/1552285.1552286"},{"key":"6_CR10","unstructured":"Gaspers, S.: Measure & conquer for parameterized branching algorithms. Parameterized Complexity News: Newsletter of the Parameterized Complexity Community (2009)"},{"key":"6_CR11","unstructured":"Gaspers, S.: Exponential Time Algorithms - Structures, Measures, and Bounds. VDM (2010)"},{"issue":"2","key":"6_CR12","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/S00453-022-01034-7","volume":"85","author":"S Gaspers","year":"2023","unstructured":"Gaspers, S., Lee, E.J.: Faster graph coloring in polynomial space. Algorithmica 85(2), 584\u2013609 (2023). https:\/\/doi.org\/10.1007\/S00453-022-01034-7","journal-title":"Algorithmica"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","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(1), 305\u2013335 (2012). https:\/\/doi.org\/10.1016\/J.JCSS.2011.05.010","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR14","doi-asserted-by":"publisher","unstructured":"Gaspers, S., Sorkin, G.B.: Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets. ACM Trans. Algorithms 13(4), 44:1\u201344:36 (2017). https:\/\/doi.org\/10.1145\/3111499","DOI":"10.1145\/3111499"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-28050-4_4","volume-title":"Parameterized and Exact Computation","author":"Y Iwata","year":"2012","unstructured":"Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 41\u201354. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28050-4_4"},{"issue":"1\u20132","key":"6_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci. 223(1\u20132), 1\u201372 (1999). https:\/\/doi.org\/10.1016\/S0304-3975(98)00017-6","journal-title":"Theor. Comput. Sci."},{"key":"6_CR17","doi-asserted-by":"publisher","unstructured":"Meijer, L.: $$3$$-coloring in time $$\\cal{O}(1.3217^n)$$. CoRR abs\/2302.13644 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2302.13644","DOI":"10.48550\/ARXIV.2302.13644"},{"key":"6_CR18","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984). https:\/\/doi.org\/10.1016\/0095-8956(84)90013-3","DOI":"10.1016\/0095-8956(84)90013-3"},{"issue":"2","key":"6_CR19","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/J.JALGOR.2004.01.001","volume":"51","author":"M Wahlstr\u00f6m","year":"2004","unstructured":"Wahlstr\u00f6m, M.: Exact algorithms for finding minimum transversals in rank-3 hypergraphs. J. Algorithms 51(2), 107\u2013121 (2004). https:\/\/doi.org\/10.1016\/J.JALGOR.2004.01.001","journal-title":"J. Algorithms"},{"key":"6_CR20","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Link\u00f6ping University, Sweden (2007)"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-540-79723-4_19","volume-title":"Parameterized and Exact Computation","author":"M Wahlstr\u00f6m","year":"2008","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 202\u2013213. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_19"},{"key":"6_CR22","doi-asserted-by":"publisher","unstructured":"Wu, P., Gu, H., Jiang, H., Shao, Z., Xu, J.: A faster algorithm for the 4-coloring problem. In: Chan, T.M., Fischer, J., Iacono, J., Herman, G. (eds.) 32nd Annual European Symposium on Algorithms, ESA 2024, 2\u20134 September 2024, Royal Holloway, London, UK. LIPIcs, vol.\u00a0308, pp. 103:1\u2013103:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2024.103","DOI":"10.4230\/LIPICS.ESA.2024.103"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.dam.2022.08.002","volume":"322","author":"E Zhu","year":"2022","unstructured":"Zhu, E., Wu, P., Shao, Z.: Exact algorithms for counting $$3$$-colorings of graphs. Discret. Appl. Math. 322, 74\u201393 (2022). https:\/\/doi.org\/10.1016\/j.dam.2022.08.002","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-2845-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T16:00:13Z","timestamp":1740067213000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-2845-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819628445","9789819628452"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-2845-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"21 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 February 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 March 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/walcom2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}