Broadcasting and Spanning Trees in de Bruijn and Kautz Networks
Broadcasting and Spanning Trees in de Bruijn and Kautz Networks
复制标题
de Bruijn 和 Kautz Networks 中的广播和生成树
DOI：
10.1016/0166-218x(92)90141-v
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
D. Sotteau
中科院分区：
文献类型：
--
作者：
M. Heydemann;J. Opatrny;D. Sotteau
证明了对任意p≤d，存在至多D⌈log p d⌉的生成有向p叉树；在De Bruijn有向图B(d，D)或直径为d的Kautz有向图K(d，D)中，这个结果直接给出了这些有向图的广播时间的一个上界Pd⌈p d⌉，改进了已知的d≥15的上界.在de Bruijn有向图的情况下，建立了B(Pq，D)的广播时间与B(p，D)和B(q，D)的广播时间的上界.这用于改进B(d，D)的广播时间的上界。我们得到了几个结果，它们是下列一般命题的改进：1.对于任意D⩾2，d⩾2，if 2kL<；d⩽2k，b(B(d，D))⩽(5 4k+3)D.2.(Ii)对于任意k⩾3，如果2 k 1<；d⩽2k，2k−1⩽b(B(d，2))⩽2k.
We prove that, for any p≤ d, there exists a spanning directed p-ary tree of depth at most D⌈ log p d⌉; in a de Bruijn digraph B (d, D) or in a Kautz digraph K (d, D) of degree d and diameter D. This result gives directly an upper bound of pD⌈ log p d⌉ on the broadcast time of these digraphs, which improves the previously known bounds for d≥ 15. In the case of de Bruijn digraphs, an upper bound on the broadcast time of B (pq, D) in terms of the broadcast times of B (p, D) and B (q, D) is established. This is used to improve the upper bounds on the broadcast time of B (d, D). We obtain several results which are refinements of the following general statements: 1.(i) for any D⩾ 2, d⩾ 2, if 2 kl< d⩽ 2 k, b (B (d, D))⩽(5 4 k+ 3) D. 2.(ii) for any k⩾ 3, if 2 k 1< d⩽ 2 k, 2k− 1⩽ b (B (d, 2))⩽ 2k.