{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:19:25Z","timestamp":1764688765945},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_8","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T07:00:50Z","timestamp":1276153250000},"page":"74-80","source":"Crossref","is-referenced-by-count":9,"title":["Capacitated Domination Faster Than O(2 n )"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization, pp. 185\u2013208 (2001)","DOI":"10.1007\/3-540-36478-1_17"},{"issue":"5","key":"8_CR2","doi-asserted-by":"publisher","first-page":"1","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\u00a056(5), 1\u201332 (2009)","journal-title":"J. ACM"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-642-04128-0_50","volume-title":"Algorithms - ESA 2009","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/exclusion meets measure and conquer: Exact algorithms for counting dominating sets. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 554\u2013565. Springer, Heidelberg (2009)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion\u2013exclusion algorithms for counting set partitions. In: Proc. FOCS\u201906, pp. 575\u2013582 (2006)","DOI":"10.1109\/FOCS.2006.41"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-540-92248-3_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Cygan","year":"2008","unstructured":"Cygan, M., Pilipczuk, M.: Faster exact bandwidth. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 101\u2013109. Springer, Heidelberg (2008)"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/3-540-44985-X_2","volume-title":"Algorithm Theory - SWAT 2000","author":"U. Feige","year":"2000","unstructured":"Feige, U.: Coping with the NP-hardness of the graph bandwidth problem. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 10\u201319. Springer, Heidelberg (2000)"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Proc. STOC\u201907, pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using m\u00f6bius inversion: Improving on steiner tree and related problems. In: Proc. ICALP\u201909, pp. 713\u2013725 (2009)","DOI":"10.1007\/978-3-642-02927-1_59"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-02927-1_8","volume-title":"Automata, Languages and Programming","author":"O. Amini","year":"2009","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Counting subgraphs via homomorphisms. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 71\u201382. Springer, Heidelberg (2009)"},{"key":"8_CR10","unstructured":"Fomin, F.V., Iwama, K., Kratsch, D.: Moderately exponential time algorithms. Dagstuhl seminar (2008)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M. Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: A parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 78\u201390. Springer, Heidelberg (2008)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Lokshtanov, D., Penninkx, E.: Planar capacitated dominating set is W[1]-hard. In: Proc. IWPEC\u201909 (to appear, 2009)","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U., Talwar, K.: Approximating the bandwidth of caterpillars. In: APPROX-RANDOM, pp. 62\u201373 (2005)","DOI":"10.1007\/11538462_6"},{"key":"8_CR15","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation by \u201clow-complexity\u201d exponential algorithms. Cahier du LAMSADE 271, LAMSADE, Universite Paris-Dauphine (2007)"},{"issue":"16","key":"8_CR16","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M. Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Inf. Process. Lett.\u00a0109(16), 957\u2013961 (2009)","journal-title":"Inf. Process. Lett."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. In: Proc. ICALP\u201909, pp. 304\u2013315 (2009)","DOI":"10.1007\/978-3-642-02927-1_26"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., Gaspers, S., Kasiviswanathan, S.P.: An exponential time 2-approximation algorithm for bandwidth. In: Proc. IWPEC\u201909 (to appear, 2009)","DOI":"10.1007\/978-3-642-11269-0_14"},{"issue":"17","key":"8_CR19","doi-asserted-by":"publisher","first-page":"3291","DOI":"10.1016\/j.dam.2008.05.035","volume":"156","author":"I. Schiermeyer","year":"2008","unstructured":"Schiermeyer, I.: Efficiency in exponential time for domination-type problems. Discrete Applied Mathematics\u00a0156(17), 3291\u20133297 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proc. FOCS\u201904, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:42:27Z","timestamp":1606167747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}