{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T06:45:21Z","timestamp":1764053121461},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_45","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T05:57:35Z","timestamp":1164779855000},"page":"439-448","source":"Crossref","is-referenced-by-count":3,"title":["Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs"],"prefix":"10.1007","author":[{"given":"Chunmei","family":"Liu","sequence":"first","affiliation":[]},{"given":"Yinglei","family":"Song","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of SODA 1999, pp. 856\u2013857 (1999)"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further Observations and Further Improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"45_CR3","unstructured":"Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proceedings of SODA 2004, pp. 788\u2013797 (2004)"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and Conquer: A Simple O(20.288\n                           n) Independent Set Algorithm. In: Proceedings of SODA 2006 (to appear, 2006)","DOI":"10.1145\/1109557.1109560"},{"issue":"5","key":"45_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Hoie, K.: Pathwidth of cubic graphs and exact algorithms. Information Processing Letters\u00a097(5), 191\u2013196 (2006)","journal-title":"Information Processing Letters"},{"key":"45_CR6","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., Krastch, D.: Measure and conquer: domination - 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":"45_CR7","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":"45_CR8","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. Freeman and Company, New York (1979)"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Grandoni, F.: A note on the complexity of minimum dominating set. Journal of Discrete Algorithms (in press)","DOI":"10.1016\/j.jda.2005.03.002"},{"key":"45_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: Approximating the minimum maximal independence number. Information Processing Letter\u00a046, 169\u2013172 (1993)","journal-title":"Information Processing Letter"},{"key":"45_CR11","unstructured":"Kann, V.: On the approximability of NP-complete optimization problems, Ph.D. Thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm (1992)"},{"key":"45_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/11604686_34","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Kneis","year":"2005","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Algorithms based on the treewidth of sparse graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 385\u2013396. Springer, Heidelberg (2005)"},{"key":"45_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Nieberg, T., Moscibroda, T., Wattenhofer, R.: Local approximation schemes for ad hoc and sensor networks. In: 2005 Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 97\u2013103 (2005)","DOI":"10.1145\/1080810.1080827"},{"key":"45_CR14","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":"45_CR15","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. Combinatorial Probabilistic Computing\u00a05, 277\u2013295 (1996)","journal-title":"Combinatorial Probabilistic Computing"},{"key":"45_CR16","unstructured":"Robson, J.M.: Finding a maximum independent set in time O(2n\/4), Technical Report 1251-01, LABRI, Universit\u00e9 Bordeaux I (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:49:58Z","timestamp":1619509798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11940128_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}