{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T16:25:12Z","timestamp":1648657512809},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2019,11,17]],"date-time":"2019-11-17T00:00:00Z","timestamp":1573948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"ANR project DESCARTES","award":["ANR-16-CE40-0023"],"award-info":[{"award-number":["ANR-16-CE40-0023"]}]},{"name":"ANR project ESTATE","award":["ANR-16 CE25-0009-03"],"award-info":[{"award-number":["ANR-16 CE25-0009-03"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We present a silent self-stabilizing distributed algorithm computing a maximal $\\ p$-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most $12\\Delta m + \\mathcal{O}(m+n)$ moves, where $m$ is the number of edges, $n$ is the number of nodes and $\\Delta $ is the maximum node degree. Regarding the time complexity, we obtain the following results: our algorithm outperforms the previously known best algorithm by a factor of $\\Delta $ with respect to the move complexity. While the round complexity for the previous algorithm was unknown, we show a $5\\big \\lfloor \\frac{n}{p+1} \\big \\rfloor +5$ bound for our algorithm.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz102","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T23:25:59Z","timestamp":1573773959000},"page":"253-266","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Silent Self-Stabilizing p-Star Decomposition\u2020"],"prefix":"10.1093","volume":"63","author":[{"given":"Mohammed","family":"Haddad","sequence":"first","affiliation":[{"name":"Universit\u00e9 Claude Bernard Lyon 1, Villeurbanne, France"}]},{"given":"Colette","family":"Johnen","sequence":"first","affiliation":[{"name":"University of Bordeaux, Talence Cedex, France"}]},{"given":"Sven","family":"K\u00f6hler","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg im Breisgau, Germany"}]}],"member":"286","published-online":{"date-parts":[[2019,11,17]]},"reference":[{"key":"2020021904592594200_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":"2020021904592594200_ref2","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-stabilization","author":"Dolev","year":"2000"},{"key":"2020021904592594200_ref3","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1017\/S0004972700040582","article-title":"Decomposition of complete graphs into stars","volume":"10","author":"Cain","year":"1974","journal-title":"Bull. Austral. Math. Soc."},{"key":"2020021904592594200_ref4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.disc.2005.04.023","article-title":"Balanced star decompositions of regular multigraphs and lambda-fold complete bipartite graphs","volume":"301","author":"Lee","year":"2005","journal-title":"Discrete Math."},{"key":"2020021904592594200_ref5","first-page":"251","article-title":"Linear star decomposition of lobster","volume":"7","author":"Merly","year":"2012","journal-title":"Int. J. Contemp. Math. Sci."},{"key":"2020021904592594200_ref6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/1097-0118(200102)36:2<59::AID-JGT1>3.0.CO;2-A","article-title":"Star factorizations of graph products","volume":"36","author":"Bryant","year":"2001","journal-title":"J. Graph Theory"},{"key":"2020021904592594200_ref7","first-page":"120","article-title":"Balanced graph partitioning","volume-title":"16th Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"Andreev","year":"2004"},{"key":"2020021904592594200_ref8","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1016\/j.comcom.2013.03.006","article-title":"Robustness study of emerged communities from exchanges in peer-to-peer networks","volume":"36","author":"Lemmouchi","year":"2013","journal-title":"Comput. Commun."},{"key":"2020021904592594200_ref9","first-page":"1002","article-title":"Parallel processing subsystems with redundancy in a distributed environment","volume-title":"6th Int. Conf. Parallel Processing and Applied Mathematics","author":"Kosowski","year":"2005"},{"key":"2020021904592594200_ref10","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1137\/140978880","article-title":"Network-based vertex dissolution","volume":"29","author":"van Bevern","year":"2015","journal-title":"SIAM J. Discrete Math."},{"key":"2020021904592594200_ref11","first-page":"23","article-title":"A grid-based parallel approach of the multi-objective branch and bound","volume-title":"15th Euromicro Int. Conf. PDP","author":"Mezmaz","year":"2007"},{"key":"2020021904592594200_ref12","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1504\/IJGUC.2009.022031","article-title":"P2P design and implementation of a parallel branch and bound algorithm for grids","volume":"1","author":"Bendjoudi","year":"2009","journal-title":"Int. J. Grid Util. Comput."},{"key":"2020021904592594200_ref13","first-page":"55","article-title":"Self-stabilizing vertex coloration and arbitrary graphs","volume-title":"4th Int. Conf. Principles of Distributed Systems international conference","author":"Gradinariu","year":"2000"},{"key":"2020021904592594200_ref14","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":"Inf. Process. Lett."},{"key":"2020021904592594200_ref15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(92)90015-N","article-title":"A self-stabilizing algorithm for maximal matching","volume":"43","author":"Hsu","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"2020021904592594200_ref16","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0020-0190(01)00171-5","article-title":"Maximal matching stabilizes in time O (m)","volume":"80","author":"Hedetniemi","year":"2001","journal-title":"Inf. Process. Lett."},{"key":"2020021904592594200_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":"2020021904592594200_ref18","first-page":"50","article-title":"Loop-free super-stabilizing spanning tree construction","volume-title":"12th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems","author":"Blin","year":"2010"},{"key":"2020021904592594200_ref19","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1137\/S0097539798427156","article-title":"Self-stabilizing algorithms for finding centers and medians of trees","volume":"29","author":"Bruell","year":"1999","journal-title":"SIAM J. Comput."},{"key":"2020021904592594200_ref20","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s004460050055","article-title":"A self-stabilizing algorithm for bridge finding","volume":"12","author":"Karaata","year":"1999","journal-title":"Distrib. Comput."},{"key":"2020021904592594200_ref21","first-page":"602","volume-title":"15th Int. Euro-Par Conf.","author":"Caron","year":"2009"},{"key":"2020021904592594200_ref22","first-page":"436","article-title":"A self-stabilizing link-cluster algorithm in mobile ad hoc networks","volume-title":"8th Int. Symposium on Parallel Architectures, Algorithms and Networks","author":"Bein","year":"2005"},{"key":"2020021904592594200_ref23","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1006\/jpdc.2001.1811","article-title":"Self-stabilizing deterministic network decomposition","volume":"62","author":"Belkouch","year":"2002","journal-title":"J. Parallel Distrib. Comput."},{"key":"2020021904592594200_ref24","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/11945529_29","article-title":"Robust self-stabilizing clustering algorithm","volume-title":"10th Int. Conf. Principles of Distributed Systems","author":"Johnen","year":"2006"},{"key":"2020021904592594200_ref25","first-page":"31","article-title":"Self-stabilizing algorithm for maximal graph partitioning into triangles","volume-title":"14th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems","author":"Neggazi","year":"2012"},{"key":"2020021904592594200_ref26","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF02278856","article-title":"A self-stabilizing algorithm for coloring planar graphs","volume":"7","author":"Ghosh","year":"1993","journal-title":"Distrib. Comput."},{"key":"2020021904592594200_ref27","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0020-0190(03)00299-0","article-title":"Linear time self-stabilizing colorings","volume":"87","author":"Hedetniemi","year":"2003","journal-title":"Inf. Process. lett."},{"key":"2020021904592594200_ref28","first-page":"240","article-title":"On the completeness of a generalized matching problem","volume-title":"10th Annual ACM Symposium on Theory of Computing","author":"Kirkpatrick","year":"1978"},{"key":"2020021904592594200_ref29","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/0212040","article-title":"On the complexity of general graph factor problems","volume":"12","author":"Kirkpatrick","year":"1983","journal-title":"SIAM J. Comput."},{"key":"2020021904592594200_ref30","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(94)90098-1","article-title":"Maximal matching stabilizes in quadratic time","volume":"49","author":"Tel","year":"1994","journal-title":"Inf. Process. Lett."},{"key":"2020021904592594200_ref31","doi-asserted-by":"crossref","DOI":"10.1109\/IPDPS.2003.1213302","article-title":"Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks","volume-title":"17th International Parallel and Distributed Processing Symposium 14","author":"Goddard","year":"2003"},{"key":"2020021904592594200_ref32","doi-asserted-by":"crossref","first-page":"1336","DOI":"10.1016\/j.tcs.2008.12.022","article-title":"A new self-stabilizing maximal matching algorithm","volume":"410","author":"Manne","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"2020021904592594200_ref33","doi-asserted-by":"crossref","first-page":"5515","DOI":"10.1016\/j.tcs.2011.05.019","article-title":"A self-stabilizing 2\/3-approximation algorithm for the maximum matching problem","volume":"412","author":"Manne","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"2020021904592594200_ref34","doi-asserted-by":"crossref","first-page":"59","DOI":"10.7155\/jgaa.00384","article-title":"An efficient silent self-stabilizing 1-maximal matching algorithm in anonymous networks","volume":"20","author":"Asada","year":"2016","journal-title":"J. Graph Algorithms Appl."},{"key":"2020021904592594200_ref35","first-page":"195","article-title":"An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon without global identifiers","volume-title":"18th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems","author":"Inoue","year":"2016"},{"key":"2020021904592594200_ref36","first-page":"74","volume-title":"15th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems","author":"Neggazi","year":"2013"},{"key":"2020021904592594200_ref37","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1016\/j.ipl.2015.05.010","article-title":"A new self-stabilizing algorithm for maximal p-star decomposition of general graphs","volume":"115","author":"Neggazi","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"2020021904592594200_ref38","doi-asserted-by":"crossref","DOI":"10.1109\/ICDCS.2007.95","article-title":"Conflict managers for self-stabilization without fairness assumption","volume-title":"27th Int. Conf. Distributed Computing Systems ICDCS\u201907","author":"Gradinariu","year":"2007"},{"key":"2020021904592594200_ref39","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1109\/12.88464","article-title":"Stabilizing communication protocols","volume":"40","author":"Gouda","year":"1991","journal-title":"IEEE Trans. Comput."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/2\/253\/32519341\/bxz102.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/2\/253\/32519341\/bxz102.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T04:59:45Z","timestamp":1582088385000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/2\/253\/5618961"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,17]]},"references-count":39,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,11,17]]},"published-print":{"date-parts":[[2020,2,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz102","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,2]]},"published":{"date-parts":[[2019,11,17]]}}}