{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T14:35:13Z","timestamp":1761921313230,"version":"3.44.0"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826696"},{"type":"electronic","value":"9783031826702"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_8","type":"book-chapter","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T04:39:55Z","timestamp":1738816795000},"page":"94-107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the\u00a0Complexity of\u00a0Minimum Membership Dominating Set"],"prefix":"10.1007","author":[{"given":"D.","family":"Karthika","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Muthucumaraswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Bentert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sriram","family":"Bhyravarapu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjay","family":"Seetharaman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Agrawal, A., Choudhary, P., Narayanaswamy, N.S., Nisha, K.K., Ramamoorthi, V.: Parameterized complexity of minimum membership dominating set. Algorithmica 85(11), 3430\u20133452 (2023)","key":"8_CR1","DOI":"10.1007\/s00453-023-01139-7"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/11533719_21","volume-title":"Computing and Combinatorics","author":"F Kuhn","year":"2005","unstructured":"Kuhn, F., von Rickenbach, P., Wattenhofer, R., Welzl, E., Zollinger, A.: Interference in cellular networks: the minimum membership set cover problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 188\u2013198. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11533719_21"},{"doi-asserted-by":"crossref","unstructured":"Michael Dom, Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Minimum membership set covering and the consecutive ones property. In Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Proceedings, volume 4059 of Lecture Notes in Computer Science, pages 339\u2013350. Springer, 2006","key":"8_CR3","DOI":"10.1007\/11785293_32"},{"doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B., Pandit, S.: Minimum membership covering and hitting. Theor. Comput. Sci. 876, 1\u201311 (2021)","key":"8_CR4","DOI":"10.1016\/j.tcs.2021.05.002"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/978-3-319-94776-1_53","volume-title":"Computing and Combinatorics","author":"NS Narayanaswamy","year":"2018","unstructured":"Narayanaswamy, N.S., Dhannya, S.M., Ramya, C.: Minimum membership hitting sets of axis parallel segments. In: Wang, L., Zhu, D. (eds.) COCOON 2018. LNCS, vol. 10976, pp. 638\u2013649. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94776-1_53"},{"issue":"3","key":"8_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"N Biggs","year":"1973","unstructured":"Biggs, N.: Perfect codes in graphs. J. Comb. Theory Ser. B 15(3), 289\u2013296 (1973)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/0095-8956(86)90079-1","volume":"40","author":"J Kratochv\u00edl","year":"1986","unstructured":"Kratochv\u00edl, J.: Perfect codes over graphs. J. Comb. Theory Ser. B 40(2), 224\u2013228 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"8_CR8","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1137\/17M1129532","volume":"32","author":"H Huang","year":"2018","unstructured":"Huang, H., Xia, B., Zhou, S.: Perfect codes in Cayley graphs. SIAM J. Discret. Math. 32(1), 548\u2013559 (2018)","journal-title":"SIAM J. Discret. Math."},{"unstructured":"Kratochv\u00edl, J.: Perfect codes in graphs and their powers. Ph.D. thesis, Ph.D. dissertation (in Czech), Charles University, Prague (1987)","key":"8_CR9"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(01)00207-1","volume":"81","author":"M Cesati","year":"2002","unstructured":"Cesati, M.: Perfect code is W[1]-complete. Inf. Process. Lett. 81(3), 163\u2013168 (2002)","journal-title":"Inf. Process. Lett."},{"key":"8_CR11","first-page":"141","volume":"3","author":"MR Fellows","year":"1991","unstructured":"Fellows, M.R., Hoover, M.N.: Perfect domination. Australas. J. Comb. 3, 141\u2013150 (1991)","journal-title":"Australas. J. Comb."},{"unstructured":"Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Comput. 1(1), 157\u2013171 (1994)","key":"8_CR12"},{"unstructured":"Telle, J.A.: Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees. Ph.D. thesis, University of Oregon (1994)","key":"8_CR13"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-030-42071-0_18","volume-title":"Treewidth, Kernels, and Algorithms","author":"JMM Rooij","year":"2020","unstructured":"Rooij, J.M.M.: Fast algorithms for join operations on tree decompositions. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms. LNCS, vol. 12160, pp. 262\u2013297. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_18"},{"doi-asserted-by":"crossref","unstructured":"Focke, J., et al.: Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pp. 3664\u20133683. SIAM (2023)","key":"8_CR15","DOI":"10.1137\/1.9781611977554.ch140"},{"issue":"18","key":"8_CR16","doi-asserted-by":"publisher","first-page":"2885","DOI":"10.1016\/j.dam.2013.06.012","volume":"161","author":"M Chellali","year":"2013","unstructured":"Chellali, M., Haynes, T.W., Hedetniemi, S.T., McRae, A.A.: [1, 2]-sets in graphs. Discret. Appl. Math. 161(18), 2885\u20132893 (2013)","journal-title":"Discret. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Meybodi, M.A., Fomin, F.V., Mouawad, A.E., Panolan, F.: On the parameterized complexity of [1, j]-domination problems. Theor. Comput. Sci. 804, 207\u2013218 (2020)","key":"8_CR17","DOI":"10.1016\/j.tcs.2019.11.032"},{"unstructured":"Reddy, S.B., Kare, A.S.: Algorithms for minimum membership dominating set problem (2024). https:\/\/arxiv.org\/abs\/2408.00797","key":"8_CR18"},{"issue":"3","key":"8_CR19","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1007\/s00453-022-01006-x","volume":"85","author":"M Kucera","year":"2023","unstructured":"Kucera, M., Such\u00fd, O.: Minimum eccentricity shortest path problem with respect to structural parameters. Algorithmica 85(3), 762\u2013782 (2023)","journal-title":"Algorithmica"},{"issue":"2","key":"8_CR20","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"8_CR21","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.dam.2020.12.010","volume":"292","author":"A Darmann","year":"2021","unstructured":"Darmann, A., D\u00f6cker, J.: On simplified NP-complete variants of monotone3-sat. Discret. Appl. Math. 292, 45\u201358 (2021)","journal-title":"Discret. Appl. Math."},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0012-365X(99)00070-9","volume":"208\u2013209","author":"P Cull","year":"1999","unstructured":"Cull, P., Nelson, I.: Error-correcting codes on the towers of Hanoi graphs. Discret. Math. 208\u2013209, 157\u2013175 (1999)","journal-title":"Discret. Math."},{"doi-asserted-by":"crossref","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96(4), 514\u2013528 (2006)","key":"8_CR24","DOI":"10.1016\/j.jctb.2005.10.006"},{"doi-asserted-by":"crossref","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000)","key":"8_CR25","DOI":"10.1142\/S0129054100000260"},{"key":"8_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T04:41:52Z","timestamp":1757133712000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}