{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T20:51:09Z","timestamp":1771102269199,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,6,4]],"date-time":"2010-06-04T00:00:00Z","timestamp":1275609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s00453-010-9418-9","type":"journal-article","created":{"date-parts":[[2010,6,3]],"date-time":"2010-06-03T15:18:50Z","timestamp":1275578330000},"page":"252-273","source":"Crossref","is-referenced-by-count":3,"title":["Branch and Recharge: Exact Algorithms for\u00a0Generalized Domination"],"prefix":"10.1007","volume":"61","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,6,4]]},"reference":[{"key":"9418_CR1","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R. Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). J. Algorithms 54, 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"key":"9418_CR2","first-page":"575","volume-title":"Inclusion-exclusion algorithms for counting set partitions","author":"A. Bj\u00f6rklund","year":"2006","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of FOCS 2006, pp. 575\u2013582. IEEE Press, New York (2006)"},{"key":"9418_CR3","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J.M. Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 547\u2013556 (2004)","journal-title":"Oper. Res. Lett."},{"key":"9418_CR4","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/jgt.20041","volume":"48","author":"J.M. Byskov","year":"2005","unstructured":"Byskov, J.M., Madsen, B.A., Skjernaa, B.: On the number of maximal bipartite subgraphs of a graph. J. Graph Theory 48, 127\u2013132 (2005)","journal-title":"J. Graph Theory"},{"key":"9418_CR5","doi-asserted-by":"crossref","first-page":"131","DOI":"10.7155\/jgaa.00064","volume":"7","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. J. Graph Algorithm Appl. 7, 131\u2013140 (2003)","journal-title":"J. Graph Algorithm Appl."},{"key":"9418_CR6","series-title":"LNCS","first-page":"192","volume-title":"Proceedings of ICALP 2005","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination\u2014a case study. In: Proceedings of ICALP 2005. LNCS, vol. 3380, pp. 192\u2013203. Springer, Berlin (2005)"},{"key":"9418_CR7","series-title":"LNCS","first-page":"508","volume-title":"Proceedings of WADS 2007","author":"F.V. Fomin","year":"2007","unstructured":"Fomin, F.V., Golovach, P., Kratsch, D., Kratochvil, J., Liedloff, M.: Branch and recharge: exact algorithms for generalized domination. In: Proceedings of WADS 2007. LNCS, vol. 4619, pp. 508\u2013519. Springer, Berlin (2007)"},{"key":"9418_CR8","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52, 293\u2013307 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"9418_CR9","doi-asserted-by":"crossref","DOI":"10.1145\/1435375.1435384","volume":"5","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"9418_CR10","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.ipl.2009.03.023","volume":"109","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Golovach, P.A., Kratochvil, J., Kratsch, D., Liedloff, M.: Sort and search: exact algorithms for generalized domination. Inf. Process. Lett. 109, 795\u2013798 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"9418_CR11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25 (2009)","journal-title":"J. ACM"},{"key":"9418_CR12","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/1109557.1109560","volume-title":"Proceedings of SODA 2006","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: A simple O(20.288n ) independent set algorithm. In: Proceedings of SODA 2006, pp. 18\u201325. SIAM, Philadelphia (2006)"},{"key":"9418_CR13","series-title":"LNCS","first-page":"1","volume-title":"Proceedings of WG 2007","author":"P. Golovach","year":"2007","unstructured":"Golovach, P., Kratochv\u00edl, J.: Computational complexity of generalized domination: a complete dichotomy for chordal graphs. In: Proceedings of WG 2007. LNCS, vol. 4769, pp. 1\u201311. Springer, Berlin (2007)"},{"key":"9418_CR14","series-title":"LNCS","first-page":"182","volume-title":"Proceedings of TAMC 2008","author":"P. Golovach","year":"2008","unstructured":"Golovach, P., Kratochv\u00edl, J.: Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. In: Proceedings of TAMC 2008. LNCS, vol. 4978, pp. 182\u2013191. Springer, Berlin (2008)"},{"key":"9418_CR15","series-title":"LNCS","first-page":"133","volume-title":"Proceedings of WG 2009","author":"P. Golovach","year":"2009","unstructured":"Golovach, P., Kratochv\u00edl, J., Such\u00fd, O.: Parameterized complexity of generalized domination problems. In: Proceedings of WG 2009. LNCS, vol. 5911, pp. 133\u2013142. Springer, Berlin (2009)"},{"key":"9418_CR16","series-title":"LNCS","first-page":"139","volume-title":"Proceedings of FSTTCS 2006","author":"S. Gupta","year":"2006","unstructured":"Gupta, S., Raman, V., Saurabh, S.: Fast exponential algorithms for Maximum r-regular induced subgraph problems. In: Proceedings of FSTTCS 2006. LNCS, vol. 4337, pp. 139\u2013151. Springer, Berlin (2006)"},{"key":"9418_CR17","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0166-218X(99)00124-9","volume":"99","author":"M.M. Halldorsson","year":"2000","unstructured":"Halldorsson, M.M., Kratochv\u00edl, J., Telle, J.A.: Independent sets with domination constraints. Discrete Appl. Math. 99, 39\u201354 (2000)","journal-title":"Discrete Appl. Math."},{"key":"9418_CR18","volume-title":"Fundamentals of Domination in Graphs","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Dekker, New York (1998)"},{"key":"9418_CR19","first-page":"128","volume":"5","author":"P. Heggernes","year":"1998","unstructured":"Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nord. J. Comput. 5, 128\u2013142 (1998)","journal-title":"Nord. J. Comput."},{"key":"9418_CR20","doi-asserted-by":"crossref","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\u201372 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9418_CR21","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5, 66\u201367 (1976)","journal-title":"Inf. Process. Lett."},{"key":"9418_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","volume":"5","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 5, 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"key":"9418_CR23","volume-title":"Discrete Mathematics and Its Applications","author":"K.H. Rosen","year":"2007","unstructured":"Rosen, K.H.: Discrete Mathematics and Its Applications. McGraw-Hill, New York (2007)"},{"key":"9418_CR24","first-page":"157","volume":"1","author":"J.A. Telle","year":"1994","unstructured":"Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Comput. 1, 157\u2013171 (1994)","journal-title":"Nord. J. Comput."},{"key":"9418_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization\u2014Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization\u2014Eureka, You Shrink! LNCS, vol. 2570, pp. 185\u2013207. Springer, Berlin (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9418-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9418-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9418-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:05Z","timestamp":1559137505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9418-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,4]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9418"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9418-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,4]]}}}