{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T16:08:46Z","timestamp":1744906126134},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_16","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"148-159","source":"Crossref","is-referenced-by-count":3,"title":["Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes"],"prefix":"10.1007","author":[{"given":"Serge","family":"Gaspers","sequence":"first","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","reference":[{"key":"16_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":"16_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"A.A. Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inform. Process. Lett.\u00a019, 37\u201340 (1984)","journal-title":"Inform. Process. Lett."},{"key":"16_CR3","series-title":"IMA, Math. Appl.,","first-page":"1","volume-title":"Graph theory and sparse matrix computation","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation. IMA, Math. Appl., vol.\u00a056, pp. 1\u201329. Springer, Heidelberg (1993)"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1006\/jagm.1999.1011","volume":"32","author":"H.L. Bodlaender","year":"1999","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Graphs with branchwidth at most three. J. Algorithms\u00a032, 167\u2013194 (1999)","journal-title":"J. Algorithms"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"K.S. Booth","year":"1982","unstructured":"Booth, K.S., Johnson, J.H.: Dominating sets in chordal graphs. SIAM J. Comput.\u00a011, 191\u2013199 (1982)","journal-title":"SIAM J. Comput."},{"key":"16_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: A survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V., Spinrad, J.P.: Graph classes: A survey. SIAM Monogr. Discrete Math. Appl., Philadelphia (1999)"},{"key":"16_CR7","unstructured":"Fomin, F.V., H\u00f8ie, K.: Pathwidth of cubic graphs and exact algorithms, Technical Report 298, Department of Informatics, University of Bergen, Norway (2005)"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"16_CR9","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. Bull. EATCS\u00a087, 47\u201377 (2005)","journal-title":"Bull. EATCS"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"16_CR11","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":"16_CR12","doi-asserted-by":"crossref","unstructured":"Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms (to appear)","DOI":"10.1016\/j.jda.2005.03.002"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0166-218X(93)90178-Q","volume":"42","author":"J.M. Keil","year":"1993","unstructured":"Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Appl. Math.\u00a042, 51\u201363 (1993)","journal-title":"Discrete Appl. Math."},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and approximation. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1142\/S0129054196000099","volume":"7","author":"T. Kloks","year":"1996","unstructured":"Kloks, T.: Treewidth of Circle Graphs. Internat. J. Found. Comput. Sci.\u00a07, 111\u2013120 (1996)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"16_CR16","unstructured":"Randerath, B., Schiermeyer, I.: Exact algorithms for Minimum Dominating Set, Technical Report zaik-469, Zentrum fur Angewandte Informatik, K\u00f6ln, Germany (2004)"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. II. Algorithmic Aspects of Tree-Width. J. Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"16_CR18","doi-asserted-by":"crossref","first-page":"33","DOI":"10.7151\/dmgt.1004","volume":"15","author":"I. Schiermeyer","year":"1995","unstructured":"Schiermeyer, I.: Problems remaining NP-complete for sparse or dense graphs. Discuss. Math. Graph Theory\u00a015, 33\u201341 (1995)","journal-title":"Discuss. Math. Graph Theory"},{"key":"16_CR19","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","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:14Z","timestamp":1619507954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11785293_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}