{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:09Z","timestamp":1780783149623,"version":"3.54.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_13","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:32Z","timestamp":1780780472000},"page":"175-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dominating Set with Quotas: Balancing Coverage and Constraints"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-5878-9975","authenticated-orcid":false,"given":"Sobyasachi","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1255-8266","authenticated-orcid":false,"given":"Sushmita","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1483-6138","authenticated-orcid":false,"given":"Sanjay","family":"Seetharaman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6283-0846","authenticated-orcid":false,"given":"Anannya","family":"Upasana","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"issue":"4","key":"13_CR1","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544\u2013556 (2009). https:\/\/doi.org\/10.1007\/s00453-008-9204-0","journal-title":"Algorithmica"},{"issue":"4","key":"13_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM (JACM) 42(4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"13_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discret. Appl. Math. 23(1), 11\u201324 (1989). https:\/\/doi.org\/10.1016\/0166-218X(89)90031-0","journal-title":"Discret. Appl. Math."},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"Banerjee, S., Eichhorn, M., Kempe, D.: Allocating with priorities and quotas: algorithms, complexity, and dynamics. In: Proceedings of the 24th ACM Conference on Economics and Computation (EC), pp. 209\u2013240 (2023). https:\/\/doi.org\/10.1145\/3580507.3597733","DOI":"10.1145\/3580507.3597733"},{"key":"13_CR5","unstructured":"Chatterjee, S., Gupta, S., Saurabh, S., Seetharaman, S., Upasana, A.: Dominating set with quotas: balancing coverage and constraints (2026). https:\/\/arxiv.org\/abs\/2604.04912"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Cygan, M.: Parameterized Algorithms. Springer. Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes. In: Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, vol. 4, pp. 157\u2013168. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2009). https:\/\/doi.org\/10.4230\/LIPICS.FSTTCS.2009.2315","DOI":"10.4230\/LIPICS.FSTTCS.2009.2315"},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/COMJNL\/BXM033","volume":"51","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J. 51(3), 292\u2013302 (2008). https:\/\/doi.org\/10.1093\/COMJNL\/BXM033","journal-title":"Comput. J."},{"issue":"4","key":"13_CR9","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995). https:\/\/doi.org\/10.1137\/S0097539792228228","journal-title":"SIAM J. Comput."},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Drange, P.G., et al.: Kernelization and sparseness: the case of dominating set. In: Ollinger, N., Vollmer, H. (eds.) 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. LIPIcs, vol. 47, pp. 31:1\u201331:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2016.31","DOI":"10.4230\/LIPICS.STACS.2016.31"},{"key":"13_CR11","doi-asserted-by":"publisher","unstructured":"Dreier, J., Eleftheriadis, I., M\u00e4hlmann, N., McCarty, R., Pilipczuk, M., Torunczyk, S.: First-order model checking on monadically stable graph classes. In: 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, pp. 21\u201330. IEEE (2024). https:\/\/doi.org\/10.1109\/FOCS61266.2024.00012","DOI":"10.1109\/FOCS61266.2024.00012"},{"key":"13_CR12","doi-asserted-by":"publisher","unstructured":"Einarson, C., Reidl, F.: A general kernelization technique for domination and independence problems in sparse classes. In: Cao, Y., Pilipczuk, M. (eds.) 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, 14\u201318 December 2020. LIPIcs, vol. 180, pp. 11:1\u201311:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2020.11","DOI":"10.4230\/LIPICS.IPEC.2020.11"},{"key":"13_CR13","doi-asserted-by":"publisher","unstructured":"Fabianski, G., Pilipczuk, M., Siebertz, S., Torunczyk, S.: Progressive algorithms for domination and independence. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. LIPIcs, vol. 126, pp. 27:1\u201327:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2019.27","DOI":"10.4230\/LIPICS.STACS.2019.27"},{"issue":"2","key":"13_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/J.IC.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., et al.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011). https:\/\/doi.org\/10.1016\/J.IC.2010.11.026","journal-title":"Inf. Comput."},{"key":"13_CR15","unstructured":"Focke, J., et al.: Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs part I: algorithmic results. CoRR abs\/2211.04278 (2022). https:\/\/doi.org\/10.48550\/ARXIV.2211.04278"},{"key":"13_CR16","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Golovach, P., Thilikos, D.M.: Contraction bidimensionality: the accurate picture. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 706\u2013717. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04128-0_63","DOI":"10.1007\/978-3-642-04128-0_63"},{"key":"13_CR17","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Linear kernels for (connected) dominating set on H-minor-free graphs. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 82\u201393. , SIAM (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.7","DOI":"10.1137\/1.9781611973099.7"},{"key":"13_CR18","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013. LIPIcs, vol. 20, pp. 92\u2013103. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2013.92","DOI":"10.4230\/LIPICS.STACS.2013.92"},{"issue":"6","key":"13_CR19","doi-asserted-by":"publisher","first-page":"1397","DOI":"10.1137\/16M1080264","volume":"49","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. SIAM J. Comput. 49(6), 1397\u20131422 (2020). https:\/\/doi.org\/10.1137\/16M1080264","journal-title":"SIAM J. Comput."},{"issue":"2","key":"13_CR20","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"FV 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(2), 281\u2013309 (2006). https:\/\/doi.org\/10.1137\/S0097539702419649","journal-title":"SIAM J. Comput."},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/J.JCSS.2016.09.002","volume":"84","author":"J Gajarsk\u00fd","year":"2017","unstructured":"Gajarsk\u00fd, J., et al.: Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84, 219\u2013242 (2017). https:\/\/doi.org\/10.1016\/J.JCSS.2016.09.002","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR22","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"13_CR23","doi-asserted-by":"publisher","unstructured":"Golovach, P.A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 195\u2013205. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92248-3_18","DOI":"10.1007\/978-3-540-92248-3_18"},{"key":"13_CR24","doi-asserted-by":"publisher","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM (JACM) 64(3), 17:1\u201317:32 (2017). https:\/\/doi.org\/10.1145\/3051095","DOI":"10.1145\/3051095"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. In: Diaz, J., Serna, M. (eds.) ESA 1996. LNCS, vol. 1136, pp. 179\u2013193. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61680-2_55","DOI":"10.1007\/3-540-61680-2_55"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. In: Arvind, V., Ramanujam, S. (eds.) FSTTCS 1998. LNCS, vol. 1530, pp. 54\u201365. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/978-3-540-49382-2_6","DOI":"10.1007\/978-3-540-49382-2_6"},{"key":"13_CR27","doi-asserted-by":"publisher","unstructured":"Gupta, S., Jain, P., Petety, A., Singh, S.: Parameterized complexity of d-Hitting set with quotas. In: Bure\u0161, T. (ed.) SOFSEM 2021. LNCS, vol. 12607, pp. 293\u2013307. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-67731-2_21","DOI":"10.1007\/978-3-030-67731-2_21"},{"issue":"2","key":"13_CR28","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/JCSS.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/JCSS.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR29","doi-asserted-by":"publisher","unstructured":"Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 41\u201354. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28050-4_4","DOI":"10.1007\/978-3-642-28050-4_4"},{"key":"13_CR30","doi-asserted-by":"publisher","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems, 9, 256\u2013278 (1974). https:\/\/doi.org\/10.1016\/S0022-0000(74)80044-9","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"13_CR31","doi-asserted-by":"publisher","unstructured":"Karthik, C.S., Laekhanukit, B., Manurangsi, P.: On the parameterized complexity of approximating dominating set. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pp. 1283\u20131296. ACM (2018). https:\/\/doi.org\/10.1145\/3188745.3188896","DOI":"10.1145\/3188745.3188896"},{"key":"13_CR32","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13:1\u201313:30 (2018). https:\/\/doi.org\/10.1145\/3170442","DOI":"10.1145\/3170442"},{"issue":"23","key":"13_CR33","doi-asserted-by":"publisher","first-page":"2536","DOI":"10.1016\/J.TCS.2010.10.045","volume":"412","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Mnich, M., Saurabh, S.: A linear kernel for planar connected dominating set. Theor. Comput. Sci. 412(23), 2536\u20132543 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2010.10.045","journal-title":"Theor. Comput. Sci."},{"key":"13_CR34","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/J.TCS.2019.11.032","volume":"804","author":"MA Meybodi","year":"2020","unstructured":"Meybodi, M.A., Fomin, F.V., Mouawad, A.E., Panolan, F.: On the parameterized complexity of [1, j]-domination problems. Theor. Comput. Sci. (TCS) 804, 207\u2013218 (2020). https:\/\/doi.org\/10.1016\/J.TCS.2019.11.032","journal-title":"Theor. Comput. Sci. (TCS)"},{"key":"13_CR35","doi-asserted-by":"publisher","unstructured":"Rooij, J.M.M.: A generic convolution algorithm for join operations on tree decompositions. In: Santhanam, R., Musatov, D. (eds.) CSR 2021. LNCS, vol. 12730, pp. 435\u2013459. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-79416-3_27","DOI":"10.1007\/978-3-030-79416-3_27"},{"key":"13_CR36","doi-asserted-by":"publisher","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 566\u2013577. Springer, Heidelberg (2009). doi: https:\/\/doi.org\/10.1007\/978-3-642-04128-0_51","DOI":"10.1007\/978-3-642-04128-0_51"},{"issue":"1","key":"13_CR37","first-page":"157","volume":"1","author":"JA Telle","year":"1994","unstructured":"Telle, J.A.: Complexity of domination-type problems in graphs. Nordic J. Comput. (NJC) 1(1), 157\u2013171 (1994)","journal-title":"Nordic J. Comput. (NJC)"},{"key":"13_CR38","doi-asserted-by":"publisher","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in biclique-free graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 802\u2013812. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_69","DOI":"10.1007\/978-3-642-33090-2_69"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:34Z","timestamp":1780780474000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}