{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:56:37Z","timestamp":1776214597925,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T00:00:00Z","timestamp":1648252800000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001691","name":"JSPS","doi-asserted-by":"publisher","award":["19H04085"],"award-info":[{"award-number":["19H04085"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"JSPS","doi-asserted-by":"publisher","award":["19K11826"],"award-info":[{"award-number":["19K11826"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"JSPS","doi-asserted-by":"publisher","award":["20H04140"],"award-info":[{"award-number":["20H04140"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJSC1606"],"award-info":[{"award-number":["JPMJSC1606"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>A self-stabilizing distributed algorithm is guaranteed eventually to reach and stay at a legitimate configuration regardless of the initial configuration of a distributed system. In this paper, we propose the generalized dominating set problem, which is a generalization of the dominating set and $k$-redundant dominating set problems. In the generalized dominating set we propose in this paper, each node $P_{i}$ is given its set of domination wish sets, and a generalized dominating set is a set of nodes such that each node is contained in the set or has a wish set in which all its members are in the set. We propose a self-stabilizing distributed algorithm for finding a minimal generalized dominating set in an arbitrary network under the unfair distributed daemon. The proposed algorithm converges in $O(n^{3}m)$ steps and $O(n)$ rounds, where $n$ (resp., $m$) is the number of nodes (resp., edges). Furthermore, it has the safe convergence property with safe convergence time in $O(1)$ rounds. The space complexity of the proposed algorithm is $O(\\Delta \\log n)$ bits per node, where $\\Delta $ is the maximum degree of nodes.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac021","type":"journal-article","created":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T07:07:54Z","timestamp":1645081674000},"page":"1452-1476","source":"Crossref","is-referenced-by-count":1,"title":["A Self-Stabilizing Distributed Algorithm for the Generalized Dominating Set Problem With Safe Convergence"],"prefix":"10.1093","volume":"66","author":[{"given":"Hisaki","family":"Kobayashi","sequence":"first","affiliation":[{"name":"Graduate School of Information Science and Technology , Osaka University, 1-5 Yamadaoka, Suita, Osaka, 565-0871,","place":["Japan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Sudo","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Sciences , Hosei University, 3-7-2 Kajino-cho, Koganei-shi, Tokyo 184-8584,","place":["Japan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hirotsugu","family":"Kakugawa","sequence":"additional","affiliation":[{"name":"Faculty of Advanced Science and Technology , Ryukoku University, 1-5 Yokotani, Seta Oe, Otsu, Shiga 520-2194,","place":["Japan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshimitsu","family":"Masuzawa","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology , Osaka University, 1-5 Yamadaoka, Suita, Osaka, 565-0871,","place":["Japan"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,3,25]]},"reference":[{"key":"2026041420053213200_ref1","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/361179.361202","article-title":"Self-stabilizing systems in spite of distributed control","volume":"17","author":"Dijkstra","year":"1974","journal-title":"Commun. ACM"},{"key":"2026041420053213200_ref2","first-page":"26","volume-title":"Proceedings of the Fifth International Workshop on Distributed Computing (IWDC)","author":"Xu","year":"2003"},{"key":"2026041420053213200_ref3","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1016\/S0898-1221(03)90143-X","article-title":"Self-stabilizing algorithms for minimal dominating sets and maximal independent sets","volume":"46","author":"Hedetniemi","year":"2003","journal-title":"Comput. Math. Appl."},{"key":"2026041420053213200_ref4","first-page":"293","volume-title":"Proceedings of the 20th IEEE International Parallel Distributed Processing Symposium (IPDPS), Workshop on Advances in Parallel and Distributed Computational Models (APDCM)","author":"Kakugawa","year":"2006"},{"key":"2026041420053213200_ref5","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.ipl.2007.02.013","article-title":"Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler","volume":"103","author":"Turau","year":"2007","journal-title":"Inform. Process. Lett."},{"key":"2026041420053213200_ref6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1142\/S0129626408003314","article-title":"Self-stabilizing graph protocols","volume":"18","author":"Goddard","year":"2008","journal-title":"Parallel Process. Lett."},{"key":"2026041420053213200_ref7","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/j.ipl.2014.04.011","article-title":"A $4n$-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon","volume":"114","author":"Chiu","year":"2014","journal-title":"Inform. Proc. Lett."},{"key":"2026041420053213200_ref8","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","article-title":"Fast distributed construction of small $k$-dominating sets and applications","volume":"28","author":"Kutten","year":"1998","journal-title":"J. Algorithms"},{"key":"2026041420053213200_ref9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0166-218X(03)00368-8","article-title":"A distributed algorithm to find k-dominating sets","volume":"141","author":"Penso","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"2026041420053213200_ref10","volume-title":"Graph Theory with Application to Algorithms and Computer Science","author":"Fink","year":"1985"},{"key":"2026041420053213200_ref11","first-page":"720","volume-title":"Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)","author":"Kamei","year":"2003"},{"key":"2026041420053213200_ref12","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1093\/ietfec\/e88-a.5.1109","article-title":"A self-stabilizing approximation algorithm for the distributed minimum k-domination","volume":"E88-A","author":"Kamei","year":"2005","journal-title":"IEICE Trans. Fundam. Electron. Commun. .Comput. Sci."},{"key":"2026041420053213200_ref13","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.camwa.2007.01.021","article-title":"A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model","volume":"54","author":"Huang","year":"2007","journal-title":"Comput. Math. Appl."},{"key":"2026041420053213200_ref14","first-page":"175","article-title":"A linear-time self-stabilizing algorithm for the minimal 2-dominating set problem in general networks","volume":"24","author":"Huang","year":"2008","journal-title":"J. Inf. Sci. Eng."},{"key":"2026041420053213200_ref15","first-page":"74","volume-title":"Proceedings of the Third International Conference on Data and Knowledge Engineering (ICDKE)","author":"Wang","year":"2012"},{"key":"2026041420053213200_ref16","first-page":"120","volume-title":"Proceedings of the 9th International Conference on Advanced Data Mining and Applications (ADMA), Lecture Notes in Computer Science, Vol. 8347","author":"Wang","year":"2013"},{"key":"2026041420053213200_ref17","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/j.jpdc.2009.11.006","article-title":"A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs","volume":"70","author":"Guellati","year":"2010","journal-title":"J. Parallel Distrib. Comput."},{"key":"2026041420053213200_ref18","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s00446-002-0078-0","article-title":"An efficient distributed algorithm for constructing small dominating sets","volume":"15","author":"Jia","year":"2002","journal-title":"Distrib. Comput."},{"key":"2026041420053213200_ref19","first-page":"378","volume-title":"Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","author":"Kobayashi","year":"2017"},{"key":"2026041420053213200_ref20","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1142\/S0129626404001970","article-title":"Distance-two information in self-stabilizing algorithms","volume":"14","author":"Gairing","year":"2004","journal-title":"Parallel Process. Lett."},{"key":"2026041420053213200_ref21","volume-title":"Two-phase commit protocol","author":"Wikipedia"},{"key":"2026041420053213200_ref22","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1016\/j.jpdc.2011.12.008","article-title":"Efficient transformation of distance-2 self-stabilizing algorithms","volume":"72","author":"Turau","year":"2012","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/6\/1452\/50643568\/bxac021.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/6\/1452\/50643568\/bxac021.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:09:41Z","timestamp":1776211781000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/6\/1452\/6554131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,25]]},"references-count":22,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,3,25]]},"published-print":{"date-parts":[[2023,6,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac021","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,6]]},"published":{"date-parts":[[2022,3,25]]}}}