Randomised distributed MIS and colouring algorithms for rings with oriented edges in bit rounds

详细信息    查看全文

• 作者：Y. Mé ; tivier ; ^{yves.metivier@labri.fr" class="auth_mail" title="E-mail the corresponding author} ; J.M. Robson ^{mike.robson@labri.fr" class="auth_mail" title="E-mail the corresponding author} ; A. Zemmari ^{akka.zemmari@labri.fr" class="auth_mail" title="E-mail the corresponding author}
• 刊名：Information and Computation
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：251
• 期：Complete
• 页码：208-214
• 全文大小：293 K

文摘

We present and analyse Las Vegas distributed algorithms which compute a MIS or a colouring for anonymous rings with an arbitrary orientation of the edges; their bit complexity and time complexity are $O(\sqrt{\log n})$ with high probability. These algorithms are optimal modulo a multiplicative constant.