{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:46:43Z","timestamp":1762325203483,"version":"3.41.2"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:p> A set [Formula: see text] of a graph [Formula: see text] is called an efficient dominating set of [Formula: see text] if every vertex [Formula: see text] has exactly one neighbor in [Formula: see text], in other words, the vertex set [Formula: see text] is partitioned to some circles with radius one such that the vertices in [Formula: see text] are the centers of partitions. A generalization of this concept, introduced by Chellali et al. [k-Efficient partitions of graphs, Commun. Comb. Optim.\u00a04 (2019) 109\u2013122], is called [Formula: see text]-efficient dominating set that briefly partitions the vertices of graph with different radiuses. It leads to a partition set [Formula: see text] such that each [Formula: see text] consists a center vertex [Formula: see text] and all the vertices in distance [Formula: see text], where [Formula: see text]. In other words, there exist the dominators with various dominating powers. The problem of finding minimum set [Formula: see text] is called the minimum [Formula: see text]-efficient domination problem. Given a positive integer [Formula: see text] and a graph [Formula: see text], the [Formula: see text]-efficient Domination Decision problem is to decide whether [Formula: see text] has a [Formula: see text]-efficient dominating set of cardinality at most [Formula: see text]. The [Formula: see text]-efficient Domination Decision problem is known to be NP-complete even for bipartite graphs [M.\u00a0Chellali, T.\u00a0W. Haynes and S.\u00a0Hedetniemi, k-Efficient partitions of graphs, Commun. Comb. Optim. \u00a04 (2019) 109\u2013122]. Clearly, every graph has a [Formula: see text]-efficient dominating set but it is not correct for efficient dominating set. In this paper, we study the following: <\/jats:p><jats:p> [Formula: see text]-efficient domination problem set is NP-complete even in chordal graphs. A polynomial-time algorithm for [Formula: see text]-efficient domination in trees. [Formula: see text]-efficient domination on sparse graphs from the parametrized complexity perspective. In particular, we show that it is [Formula: see text]-hard on d-degenerate graphs while the original dominating set has Fixed Parameter Tractable (FPT) algorithm on d-degenerate graphs. [Formula: see text]-efficient domination on nowhere-dense graphs is FPT. <\/jats:p>","DOI":"10.1142\/s1793830922500513","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T15:24:18Z","timestamp":1642087458000},"source":"Crossref","is-referenced-by-count":2,"title":["k-Efficient domination: Algorithmic perspective"],"prefix":"10.1142","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2089-0250","authenticated-orcid":false,"given":"Mohsen Alambardar","family":"Meybodi","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Statistics, Department of Applied Mathematics and Computer Science, University of Isfahan, Isfahan 81746-73441, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"issue":"4","key":"S1793830922500513BIB001","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"Alon N.","year":"2009","journal-title":"Algorithmica"},{"key":"S1793830922500513BIB002","first-page":"189","volume":"189","author":"Bange D.","year":"1988","journal-title":"Appl. Discrete Math."},{"key":"S1793830922500513BIB003","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830919500162"},{"issue":"3","key":"S1793830922500513BIB004","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"Biggs N.","year":"1973","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"S1793830922500513BIB005","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0166-218X(94)00138-4","volume":"66","author":"Chain-Chin Y.","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"S1793830922500513BIB006","first-page":"109","volume":"4","author":"Chellali M.","year":"2019","journal-title":"Commun. Comb. Optim."},{"key":"S1793830922500513BIB007","series-title":"FSTTCS","first-page":"157","volume-title":"IARCS Annual Conf. Foundations of Software Technology and Theoretical Computer Science","volume":"4","author":"Dawar A.","year":"2009"},{"issue":"4","key":"S1793830922500513BIB008","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"Downey R. G.","year":"1995","journal-title":"SIAM J. Comput."},{"key":"S1793830922500513BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"S1793830922500513BIB010","volume-title":"Computers and Intractability","volume":"174","author":"Garey M. R.","year":"1979"},{"key":"S1793830922500513BIB011","first-page":"21","volume-title":"33rd International Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Grohe M.","year":"2013"},{"key":"S1793830922500513BIB012","doi-asserted-by":"crossref","DOI":"10.1201\/9781482246582","volume-title":"undamentals of Domination in Graphs","author":"Haynes T. W.","year":"2013"},{"key":"S1793830922500513BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6525-6"},{"key":"S1793830922500513BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830920500573"},{"issue":"04","key":"S1793830922500513BIB015","doi-asserted-by":"crossref","first-page":"1650067","DOI":"10.1142\/S1793830916500671","volume":"8","author":"Krishnakumari B.","year":"2016","journal-title":"Discrete Math. Algorithms Appl."},{"volume-title":"Perfect Dominating Sets","year":"1990","author":"Livingston M.","key":"S1793830922500513BIB016"},{"issue":"1","key":"S1793830922500513BIB017","first-page":"163","volume":"11","author":"Lu C. L.","year":"2002","journal-title":"Discrete Appl. Math."},{"key":"S1793830922500513BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830920500688"},{"issue":"03","key":"S1793830922500513BIB019","doi-asserted-by":"crossref","first-page":"1250045","DOI":"10.1142\/S1793830912500450","volume":"4","author":"Pradhan D.","year":"2012","journal-title":"Discrete Math. Algorithms Appl."},{"key":"S1793830922500513BIB020","first-page":"802","volume-title":"Proc. 20th Annual European Symp. Algorithms","author":"Telle J. A.","year":"2012"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830922500513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T05:54:27Z","timestamp":1669701267000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830922500513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":20,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["10.1142\/S1793830922500513"],"URL":"https:\/\/doi.org\/10.1142\/s1793830922500513","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"article-number":"2250051"}}