{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T19:04:00Z","timestamp":1757703840676},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642145520"},{"type":"electronic","value":"9783642145537"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14553-7_19","type":"book-chapter","created":{"date-parts":[[2010,7,26]],"date-time":"2010-07-26T07:59:21Z","timestamp":1280131161000},"page":"185-196","source":"Crossref","is-referenced-by-count":7,"title":["Approximation Algorithms for the Capacitated Domination Problem"],"prefix":"10.1007","author":[{"given":"Mong-Jen","family":"Kao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Han-Lin","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"19_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(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"3","key":"19_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM\u00a051(3), 363\u2013384 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"19_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. The Computer Journal\u00a051(3) (2008)","DOI":"10.1093\/comjnl\/bxm037"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04(3), 233\u2013235","DOI":"10.1287\/moor.4.3.233"},{"issue":"6","key":"19_CR6","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM\u00a052(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M. Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: A parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 78\u201390. Springer, Heidelberg (2008)"},{"key":"19_CR8","doi-asserted-by":"publisher","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. Springer, Heidelberg (1999)"},{"issue":"4","key":"19_CR9","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(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"19_CR10","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"2","key":"19_CR11","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput.\u00a036(2), 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Automata, Languages and Programming","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for np-hard problems on planar graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"issue":"4","key":"19_CR13","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"T.W. Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discret. Math.\u00a015(4), 519\u2013529 (2002)","journal-title":"SIAM J. Discret. Math."},{"key":"19_CR14","volume-title":"Fundamentals of Domination in Graphs (Pure and Applied Mathematics)","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs (Pure and Applied Mathematics). Marcel Dekker, New York (1998)"},{"issue":"3","key":"19_CR15","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing\u00a011(3), 555\u2013556 (1982)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"19_CR16","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM\u00a021(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/800125.804034","volume-title":"STOC 1973: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing","author":"D.S. Johnson","year":"1973","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: STOC 1973: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pp. 38\u201349. ACM Press, New York (1973)"},{"key":"19_CR18","unstructured":"Kao, M.-J., Chen, H.-L.: Approximation algorithms for the capacitated domination problem (manuscript) (2010), http:\/\/arxiv.org\/abs\/1004.2839"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Kao, M.-J., Liao, C.-S., Lee, D.T.: Capacitated domination problem. Algorithmica (2009)","DOI":"10.1007\/s00453-009-9336-x"},{"key":"19_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1007\/11533719_83","volume-title":"Computing and Combinatorics","author":"C.-S. Liao","year":"2005","unstructured":"Liao, C.-S., Lee, D.-T.: Power domination problem in graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 818\u2013828. Springer, Heidelberg (2005)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers (1975)","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"19_CR23","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Roberts, F.S.: Graph Theory and Its Applications to Problems of Society (1978)","DOI":"10.1137\/1.9781611970401"},{"issue":"2","key":"19_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1142\/S0129054103001753","volume":"14","author":"P.-J. Wan","year":"2003","unstructured":"Wan, P.-J., Alzoubi, K.M., Frieder, O.: A simple heuristic for minimum connected dominating set in graphs. International Journal of Foundations of Computer Science\u00a014(2), 323\u2013333 (2003)","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14553-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T16:30:22Z","timestamp":1559320222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14553-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642145520","9783642145537"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14553-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}