Broadcasting and gossiping on de Bruijn, shuffle-exchange and similar networks

摘要

We use simple compound properties of de Bruijn related networks to get new bounds about broadcasting and gossiping on such networks. Some asymptotically optimal results on undirected de Bruijn, Kautz, and generalized shuffle-exchange networks are obtained. Our techniques can also be used to derive efficient broadcasting protocols for the undirected graph associated to a line digraph. We give asymptotically optimal broadcast algorithms for some of the generalized de Bruijn and Kautz graphs and an asymptotically optimal gossiping protocol in full duplex model for the shuffle-exchange graph. (C) 1998 Elsevier Science B.V. All rights reserved. [References: 26]