{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T14:32:25Z","timestamp":1761921145763},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"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":["Algorithmica"],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1007\/s00453-023-01139-7","type":"journal-article","created":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T14:02:49Z","timestamp":1686664969000},"page":"3430-3452","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Complexity of Minimum Membership Dominating Set"],"prefix":"10.1007","volume":"85","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"Pratibha","family":"Choudhary","sequence":"additional","affiliation":[]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[]},{"given":"K. K.","family":"Nisha","sequence":"additional","affiliation":[]},{"given":"Vijayaragunathan","family":"Ramamoorthi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,13]]},"reference":[{"key":"1139_CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"1139_CR2","volume-title":"Fundamentals of Domination in Graphs. Pure and Applied Mathematics","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Pure and Applied Mathematics, vol. 208. Dekker, New York (1998)"},{"key":"1139_CR3","doi-asserted-by":"crossref","unstructured":"Kuhn, F., von Rickenbach, P., Wattenhofer, R., Welzl, E., Zollinger, A.: Interference in cellular networks: The minimum membership set cover problem. In: Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16\u201329, 2005, Proceedings, pp. 188\u2013198 (2005)","DOI":"10.1007\/11533719_21"},{"key":"1139_CR4","volume-title":"WALCOM: Algorithms and Computation","author":"A Agrawal","year":"2022","unstructured":"Agrawal, A., Choudhary, P., Narayanaswamy, N.S., Nisha, K.K., Ramamoorthi, V.: Parameterized complexity of minimum membership dominating set. In: Mutzel, P., Rahman, M.S., Slamin (eds.) WALCOM: Algorithms and Computation. Springer, Cham (2022)"},{"key":"1139_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth: Algorithmic techniques and results. In: Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS\u201997, Bratislava, Slovakia, August 25\u201329, 1997, Proceedings, pp. 19\u201336 (1997)","DOI":"10.1007\/BFb0029946"},{"issue":"1","key":"1139_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1139_CR7","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make w-hard problems hard: Fpt algorithms for w-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"key":"1139_CR8","unstructured":"Belmonte, R., Ghadikolaei, M.K., Kiyomi, M., Lampis, M., Otachi, Y.: How bad is the freedom to flood-it. In: 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, pp. 5\u20131513. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"key":"1139_CR9","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22\u201325, 1992, pp. 36\u201349 (1992)"},{"key":"1139_CR10","doi-asserted-by":"crossref","unstructured":"Dom, M., Guo, J., Niedermeier, R., Wernicke, S.: Minimum membership set covering and the consecutive ones property. In: Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Riga, Latvia, July 6\u20138, 2006, Proceedings, pp. 339\u2013350 (2006)","DOI":"10.1007\/11785293_32"},{"key":"1139_CR11","doi-asserted-by":"crossref","unstructured":"Dhannya, S.M., Narayanaswamy, N.S., Ramya, C.: Minimum membership hitting sets of axis parallel segments. In: Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2\u20134, 2018, Proceedings, pp. 638\u2013649 (2018)","DOI":"10.1007\/978-3-319-94776-1_53"},{"key":"1139_CR12","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B., Pandit, S.: Minimum membership covering and hitting. In: WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27\u2013March 2, 2019, Proceedings, pp. 394\u2013406 (2019)","DOI":"10.1007\/978-3-030-10564-8_31"},{"issue":"3","key":"1139_CR13","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 Se. B 15(3), 289\u2013296 (1973)","journal-title":"J. Comb. Theory Se. B"},{"key":"1139_CR14","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."},{"issue":"1","key":"1139_CR15","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."},{"issue":"2","key":"1139_CR16","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"},{"key":"1139_CR17","unstructured":"Kratochv\u00edl, J.: Perfect codes in graphs and their powers. PhD dissertation(in czech), Charles University, Prague (1987)"},{"key":"1139_CR18","doi-asserted-by":"crossref","unstructured":"Kratochv\u00edl, J., Kriv\u00e1nek, M.: On the computational complexity of codes in graphs. In: Mathematical Foundations of Computer Science 1988, MFCS\u201988, Carlsbad, Czechoslovakia, August 29+-September 2, 1988, Proceedings. Lecture Notes in Computer Science, vol. 324, pp. 396\u2013404. Springer, Berlin Heidelberg (1988)","DOI":"10.1007\/BFb0017162"},{"issue":"3","key":"1139_CR19","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1016\/j.ejc.2010.11.007","volume":"32","author":"M Mollard","year":"2011","unstructured":"Mollard, M.: On perfect codes in cartesian products of graphs. Eur. J. Comb. 32(3), 398\u2013403 (2011)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"1139_CR20","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."},{"issue":"1","key":"1139_CR21","first-page":"157","volume":"1","author":"JA Telle","year":"1994","unstructured":"Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Comput. 1(1), 157\u2013171 (1994)","journal-title":"Nord. J. Comput."},{"key":"1139_CR22","unstructured":"Telle, J.A.: Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees. PhD thesis, USA (1994). UMI Order No. GAX95-02388"},{"key":"1139_CR23","unstructured":"Chapelle, M.: Parameterized complexity of generalized domination problems on bounded tree-width graphs. CoRR arXiv:1004.2642 (2010)"},{"issue":"18","key":"1139_CR24","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."},{"key":"1139_CR25","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. 804, 207\u2013218 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1139_CR26","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition. Graduate texts in mathematics, vol. 173. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"1139_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, 1st edn. Springer, New York (2015)","edition":"1"},{"key":"1139_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"issue":"2","key":"1139_CR29","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is np-hard. J. ACM 55(2), 11\u201311129 (2008)","journal-title":"J. ACM"},{"key":"1139_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"1139_CR31","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, P., Eiben, E., Ganian, R., Knop, D., Ordyniak, S.: Solving integer linear programs with a small number of global variables and constraints. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 607\u2013613 (2017)","DOI":"10.24963\/ijcai.2017\/85"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01139-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01139-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01139-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T19:03:21Z","timestamp":1698779001000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01139-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":31,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1139"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01139-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]},"assertion":[{"value":"25 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}