{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:02:04Z","timestamp":1760079724181},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T00:00:00Z","timestamp":1384214400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00453-013-9844-6","type":"journal-article","created":{"date-parts":[[2013,11,11]],"date-time":"2013-11-11T17:56:11Z","timestamp":1384192571000},"page":"1-43","source":"Crossref","is-referenced-by-count":12,"title":["Capacitated Domination: Problem Complexity and Approximation Algorithms"],"prefix":"10.1007","volume":"72","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"}]},{"given":"D. T.","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,12]]},"reference":[{"key":"9844_CR1","doi-asserted-by":"crossref","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 33, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"9844_CR2","doi-asserted-by":"crossref","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 51, 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"9844_CR3","doi-asserted-by":"crossref","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 41, 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"9844_CR4","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1145\/167088.167161","volume-title":"Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC\u201993)","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC\u201993), pp.\u00a0226\u2013234. ACM, New York (1993)"},{"key":"9844_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9844_CR6","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51, 255\u2013269 (2008)","journal-title":"Comput. J."},{"key":"9844_CR7","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(01)00069-4","volume":"23","author":"P. Bose","year":"2002","unstructured":"Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom. Theory Appl. 23, 303\u2013312 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9844_CR8","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37, 1077\u20131106 (2007)","journal-title":"SIAM J. Comput."},{"key":"9844_CR9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"F.A. Chudak","year":"2005","unstructured":"Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102, 207\u2013222 (2005)","journal-title":"Math. Program."},{"key":"9844_CR10","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1137\/S0097539703422479","volume":"36","author":"J. Chuzhoy","year":"2006","unstructured":"Chuzhoy, J.: Covering problems with hard capacities. SIAM J. Comput. 36, 498\u2013515 (2006)","journal-title":"SIAM J. Comput."},{"key":"9844_CR11","first-page":"74","volume-title":"Proceedings of the 12th Scandinavian Conference on Algorithm Theory (SWAT\u201910)","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than O(2 n ). In: Proceedings of the 12th Scandinavian Conference on Algorithm Theory (SWAT\u201910), pp. 74\u201380. Springer, Berlin (2010)"},{"key":"9844_CR12","doi-asserted-by":"crossref","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 52, 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"9844_CR13","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Proceedings of the 3rd International Conference on Parameterized and Exact Computation (IWPEC\u201908)","author":"M. Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Proceedings of the 3rd International Conference on Parameterized and Exact Computation (IWPEC\u201908), pp. 78\u201390. Springer, Heidelberg (2008)"},{"key":"9844_CR14","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.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9844_CR15","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9844_CR16","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"M.R. Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209, 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"key":"9844_CR17","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9844_CR18","doi-asserted-by":"crossref","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. 36, 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"9844_CR19","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jcss.2005.06.004","volume":"72","author":"R. Gandhi","year":"2006","unstructured":"Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72, 16\u201333 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9844_CR20","first-page":"323","volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902)","author":"R. Gandhi","year":"2002","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902), pp. 323\u2013332. IEEE Comput. Soc., Washington (2002)"},{"key":"9844_CR21","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, New York (1979)"},{"key":"9844_CR22","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0196-6774(03)00053-1","volume":"48","author":"S. Guha","year":"2003","unstructured":"Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. J. Algorithms 48, 257\u2013270 (2003)","journal-title":"J. Algorithms"},{"key":"9844_CR23","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Proceedings of the 34th International Conference on Automata, Languages and Programming (ICALP\u201907)","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Proceedings of the 34th International Conference on Automata, Languages and Programming (ICALP\u201907), pp. 375\u2013386. Springer, Berlin (2007)"},{"key":"9844_CR24","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-642-28050-4_15","volume-title":"Proceedings of the 6th International Conference on Parameterized and Exact Computation (IPEC\u201911)","author":"T. Hagerup","year":"2012","unstructured":"Hagerup, T.: Simpler linear-time kernelization for planar dominating set. In: Proceedings of the 6th International Conference on Parameterized and Exact Computation (IPEC\u201911), pp. 181\u2013193. Springer, Berlin (2012)"},{"key":"9844_CR25","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). Dekker, New York (1998)"},{"key":"9844_CR26","doi-asserted-by":"crossref","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. Discrete Math. 15, 519\u2013529 (2002)","journal-title":"SIAM J. Discrete Math."},{"key":"9844_CR27","doi-asserted-by":"crossref","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 J. Comput. 11, 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"key":"9844_CR28","first-page":"549","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J.\u00a0ACM 21, 549\u2013568 (1974)","journal-title":"J.\u00a0ACM"},{"key":"9844_CR29","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"9844_CR30","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1137\/1.9781611973099.57","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"F. Kammer","year":"2012","unstructured":"Kammer, F., Tholey, T.: Approximate tree decompositions of planar graphs in linear time. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912), pp. 683\u2013698. SIAM, Philadelphia (2012)"},{"key":"9844_CR31","first-page":"185","volume-title":"FAW 2010","author":"M.-J. Kao","year":"2010","unstructured":"Kao, M.-J., Chen, H.-L.: Approximation algorithms for the capacitated domination problem. In: FAW 2010, pp. 185\u2013196. Springer, Berlin (2010)"},{"key":"9844_CR32","first-page":"494","volume-title":"Proceedings of the 22nd International Conference on Algorithms and Computation (ISAAC\u201911)","author":"M.-J. Kao","year":"2011","unstructured":"Kao, M.-J., Lee, D.T.: Capacitated domination: constant factor approximations for planar graphs. In: Proceedings of the 22nd International Conference on Algorithms and Computation (ISAAC\u201911), pp.\u00a0494\u2013503. Springer, Berlin (2011)"},{"key":"9844_CR33","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/s00453-009-9336-x","volume":"60","author":"M.-J. Kao","year":"2011","unstructured":"Kao, M.-J., Liao, C.-S., Lee, D.T.: Capacitated domination problem. Algorithmica 60, 274\u2013300 (2011)","journal-title":"Algorithmica"},{"key":"9844_CR34","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. Lecture Notes in Computer Science, vol.\u00a0842. Springer, Berlin (1994)"},{"key":"9844_CR35","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1007\/11533719_83","volume-title":"Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON\u201905)","author":"C.-S. Liao","year":"2005","unstructured":"Liao, C.-S., Lee, D.-T.: Power domination problem in graphs. In: Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON\u201905), pp. 818\u2013828. Springer, Berlin (2005)"},{"key":"9844_CR36","unstructured":"Liedloff, M., Todinca, I., Villanger, Y.: Solving capacitated dominating set by using covering by subsets and maximum matching. Discrete Appl. Math. (2012)"},{"key":"9844_CR37","doi-asserted-by":"crossref","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":"9844_CR38","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1109\/SFCS.2001.959907","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS\u201901)","author":"M. P\u00e1l","year":"2001","unstructured":"P\u00e1l, M., Tardos, E., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS\u201901), p.\u00a0329. IEEE Comput. Soc., Washington (2001)"},{"key":"9844_CR39","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970401","volume-title":"Graph Theory and Its Applications to Problems of Society","author":"F.S. Roberts","year":"1978","unstructured":"Roberts, F.S.: Graph Theory and Its Applications to Problems of Society (1978)"},{"key":"9844_CR40","first-page":"265","volume-title":"STOC 1997","author":"D.B. Shmoys","year":"1997","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: STOC 1997, pp. 265\u2013274. ACM, New York (1997)"},{"key":"9844_CR41","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/978-3-642-28050-4_16","volume-title":"Proceedings of the 6th International Conference on Parameterized and Exact Computation (IPEC\u201911)","author":"R. Bevern van","year":"2012","unstructured":"van Bevern, R., Hartung, S., Kammer, F., Niedermeier, R., Weller, M.: Linear-time computation of a linear problem kernel for dominating set on planar graphs. In: Proceedings of the 6th International Conference on Parameterized and Exact Computation (IPEC\u201911), pp. 194\u2013206. Springer, Berlin (2012)"},{"key":"9844_CR42","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"},{"key":"9844_CR43","doi-asserted-by":"crossref","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. Int. J. Found. Comput. Sci. 14, 323\u2013333 (2003)","journal-title":"Int. J. Found. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9844-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9844-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9844-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T12:53:05Z","timestamp":1564663985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9844-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,12]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9844"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9844-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,12]]}}}