{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:03Z","timestamp":1725558963395},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241324"},{"type":"electronic","value":"9783540305590"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_21","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"245-256","source":"Crossref","is-referenced-by-count":64,"title":["Exact (Exponential) Algorithms for the Dominating Set Problem"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2\u22122\/(k+1))\n n\n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289, 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"21_CR3","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"21_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.\u00a02125, pp. 462\u2013470. Springer, Heidelberg (2001)"},{"unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branchwidth and exponential speed-up. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 168\u2013177 (2003)","key":"21_CR5"},{"key":"21_CR6","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco (1979)"},{"key":"21_CR7","volume-title":"Algorithmic graph theory and perfect graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press, New York (1980)"},{"key":"21_CR8","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. Marcel Dekker Inc., New York (1998)"},{"key":"21_CR9","volume-title":"Domination in graphs: Advanced Topics","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in graphs: Advanced Topics. Marcel Dekker Inc., New York (1998)"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences\u00a063, 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Johnson, D.S., Szegedy, M.: What are the least tractable instances of max independent set? In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 927\u2013928 (1999)","key":"21_CR11"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1017\/S0963548300002042","volume":"5","author":"B. Reed","year":"1996","unstructured":"Reed, B.: Paths, stars and the number three. Combinatorics, Probability and Computing\u00a05, 277\u2013295 (1996)","journal-title":"Combinatorics, Probability and Computing"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. Journal of Algorithms\u00a07, 425\u2013440 (1986)","journal-title":"Journal of Algorithms"},{"key":"21_CR14","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)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:30:00Z","timestamp":1620012600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}