{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T12:26:16Z","timestamp":1754483176019},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797227"},{"type":"electronic","value":"9783540797234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-79723-4_20","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T06:22:17Z","timestamp":1210054937000},"page":"214-225","source":"Crossref","is-referenced-by-count":13,"title":["Exact Algorithms for Edge Domination"],"prefix":"10.1007","author":[{"given":"Johan M. M.","family":"van Rooij","sequence":"first","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1023\/A:1011445210568","volume":"5","author":"R. Carr","year":"2001","unstructured":"Carr, R., Fujito, T., Konjevod, G., Parekh, O.: A \n                  \n                    \n                  \n                  $2\\frac{1}{10}$\n                 approximation algorithm for a generalization of the weighted edge-dominating set problem. Journal of Combinatorial Optimization\u00a05, 317\u2013326 (2001)","journal-title":"Journal of Combinatorial Optimization"},{"key":"20_CR2","first-page":"161","volume":"87","author":"R.G. Downey","year":"1992","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. Congressus Numerantium\u00a087, 161\u2013178 (1992)","journal-title":"Congressus Numerantium"},{"key":"20_CR3","unstructured":"Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 781\u2013790 (2004)"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/11847250_13","volume-title":"Parameterized and Exact Computation","author":"H. Fernau","year":"2006","unstructured":"Fernau, H.: Edge dominating set: Efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 140\u2013151. Springer, Heidelberg (2006)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/11940128_4","volume-title":"Algorithms and Computation","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Branching and treewidth based exact algorithms. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 16\u201325. Springer, Heidelberg (2006)"},{"key":"20_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 \u2014 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":"20_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":"20_CR9","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1969)"},{"key":"20_CR10","first-page":"196","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. SIAM\u00a010, 196\u2013210 (1962)","journal-title":"J. SIAM"},{"key":"20_CR11","first-page":"61","volume":"82","author":"K. Iwama","year":"2004","unstructured":"Iwama, K.: Worst-case upper bounds for kSAT. Bulletin of the EATCS\u00a082, 61\u201371 (2004)","journal-title":"Bulletin of the EATCS"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Information Processing Letters\u00a027, 119\u2013123 (1988)","journal-title":"Information Processing Letters"},{"key":"20_CR13","doi-asserted-by":"publisher","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. Information Processing Letters\u00a05, 66\u201367 (1976)","journal-title":"Information Processing Letters"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"E.L. Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput.\u00a09, 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math.\u00a03, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0166-218X(99)00052-9","volume":"92","author":"J. Plesn\u00edk","year":"1999","unstructured":"Plesn\u00edk, J.: Constrained weighted matchings and edge coverings in graphs. Disc. Appl. Math.\u00a092, 229\u2013241 (1999)","journal-title":"Disc. Appl. Math."},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00224-007-1334-2","volume":"42","author":"V. Raman","year":"2007","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theory of Computing Systems\u00a042, 563\u2013587 (2007)","journal-title":"Theory of Computing Systems"},{"key":"20_CR18","unstructured":"Randerath, B., Schiermeyer, I.: Exact algorithms for minimum dominating set. Technical Report zaik2005-501, Universit\u00e4t zu K\u00f6ln, Cologne, Germany (2005)"},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11785293_17","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"I. Razgon","year":"2006","unstructured":"Razgon, I.: Exact computation of maximum induced forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 160\u2013171. Springer, Heidelberg (2006)"},{"key":"20_CR20","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. J. Algorithms\u00a07, 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"20_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)"},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.: Finding a maximum independent set. SIAM J. Comput.\u00a06, 537\u2013546 (1977)","journal-title":"SIAM J. Comput."},{"key":"20_CR23","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for edge domination. Technical Report UU-CS-2007-051, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands (2007)"},{"key":"20_CR24","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer: A faster exact algorithm for dominating set. In: Proc. 24st Symp. Theoretical Aspects of Computer Science (STACS 2008) (2008)"},{"key":"20_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1007\/11682462_73","volume-title":"LATIN 2006: Theoretical Informatics","author":"Y. Villanger","year":"2006","unstructured":"Villanger, Y.: Improved exponential-time algorithms for treewidth and minimum fill-in. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 800\u2013811. Springer, Heidelberg (2006)"},{"key":"20_CR26","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)"},{"key":"20_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-540-28639-4_25","volume-title":"Parameterized and Exact Computation","author":"G.J. Woeginger","year":"2004","unstructured":"Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems (invited talk). In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 281\u2013290. Springer, Heidelberg (2004)"},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math.\u00a038, 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79723-4_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,1]],"date-time":"2019-03-01T15:59:55Z","timestamp":1551455995000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79723-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540797227","9783540797234"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79723-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}