{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:14:19Z","timestamp":1726409659294},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_18","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"165-175","source":"Crossref","is-referenced-by-count":0,"title":["Counting Minimum Weighted Dominating Sets"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexey A.","family":"Stepanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/978-3-540-45193-8_6","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"O. Angelsmark","year":"2003","unstructured":"Angelsmark, O., Jonsson, P.: Improved algorithms for counting solutions in constraint satisfaction problems. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 81\u201395. Springer, Heidelberg (2003)"},{"issue":"4","key":"18_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0020-0190(96)00159-7","volume":"60","author":"E.T. Bax","year":"1996","unstructured":"Bax, E.T., Franklin, J.A: finite-difference sieve to count paths and cycles by length. Inf. Process. Lett.\u00a060(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"18_CR3","first-page":"575","volume-title":"FOCS 2006","author":"A. Bj\u00f6rklund","year":"2006","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: FOCS 2006. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 575\u2013582. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"18_CR4","series-title":"Society for Industrial and Applied Mathematics","first-page":"292","volume-title":"SODA\u00a02002","author":"V. Dahll\u00f6f","year":"2002","unstructured":"Dahll\u00f6f, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: SODA\u00a02002. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 292\u2013298. ACM Press, New York (2002)"},{"issue":"1-3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V. Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2 SAT and 3 SAT formulae. Theoretical Computer Science 332\u00a0332(1-3), 265\u2013291 (2005)","journal-title":"Theoretical Computer Science 332"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/11602613_58","volume-title":"Algorithms and Computation","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Branching and treewidth based exact algorithms. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 16\u201325. Springer, Heidelberg (2005)"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/11523468_16","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: Domination \u2013 a case study. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 191\u2013203. Springer, Heidelberg (2005)"},{"key":"18_CR8","first-page":"47","volume":"87","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the EATCS\u00a087, 47\u201377 (2005)","journal-title":"Bulletin of the EATCS"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/11602613_58","volume-title":"Algorithms and Computation","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Bounding the number of minimal dominating sets: a measure and conquer approach. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 573\u2013582. Springer, Heidelberg (2005)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/978-3-540-30559-0_21","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 245\u2013256. Springer, Heidelberg (2004)"},{"key":"18_CR11","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. Electronic Colloquium on Computational Complexity (ECCC) 33 (2005)"},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.jda.2005.03.002","volume":"4","author":"F. Grandoni","year":"2006","unstructured":"Grandoni, F.: A note on the complexity of minimum dominating set. Journal of Discrete Algorithms\u00a04(2), 209\u2013214 (2006)","journal-title":"Journal of Discrete Algorithms"},{"key":"18_CR13","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","volume-title":"Domination in graphs","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T.: Domination in graphs (Advanced topics). Monographs and Textbooks in Pure and Applied Mathematics, vol.\u00a0209. Marcel Dekker Inc., New York (1998)"},{"issue":"4","key":"18_CR14","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Stearns, R.E.: The complexity of planar counting problems. SIAM Journal on Computing\u00a027(4), 1142\u20131167 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR15","series-title":"Lectures in Mathematics ETH Z\u00fcrich","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, sampling and integrating: algorithms and complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Z\u00fcrich. Birkh\u00e4user Verlag, Basel (2003)"},{"issue":"1981\/82","key":"18_CR16","first-page":"49","volume":"2","author":"R.M. Karp","year":"1981","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters 1\u00a02(1981\/82), 49\u201351 (1981)","journal-title":"Operations Research Letters 1"},{"key":"18_CR17","first-page":"583","volume-title":"FOCS 2006","author":"M. Koivisto","year":"2006","unstructured":"Koivisto, M.: An O(2 n ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In: FOCS 2006. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 583\u2013590. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/11753728_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"D. M\u00f6lle","year":"2006","unstructured":"M\u00f6lle, D., Richter, S., Rossmanith, P.: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, pp. 270\u2013280. Springer, Heidelberg (2006)"},{"key":"18_CR19","unstructured":"Randerath, B., Schiermeyer, I.: Exact algorithms for MINIMUM DOMINATING SET. Technical Report zaik-469, Zentrum f\u00fcr Angewandte Informatik K\u00f6ln, Germany (2004)"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Ryser, H.J.: Combinatorial mathematics. The Carus Mathematical Monographs, No. 14. Published by The Mathematical Association of America (1963)","DOI":"10.5948\/UPO9781614440147"},{"key":"18_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/978-3-540-31856-9_3","volume-title":"STACS 2005","author":"U. Sch\u00f6ning","year":"2005","unstructured":"Sch\u00f6ning, U.: Algorithmics in exponential time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 36\u201343. Springer, Heidelberg (2005)"},{"issue":"2","key":"18_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"18_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"},{"issue":"1","key":"18_CR24","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(95)00144-1","volume":"155","author":"W. Zhang","year":"1996","unstructured":"Zhang, W.: Number of models and satisfiability of sets of clauses. Theoretical Computer Science\u00a0155(1), 277\u2013288 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T23:49:45Z","timestamp":1629589785000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}