Broadcasting and spanning trees in de Bruijn and Kautz networks

Broadcasting and spanning trees in de Bruijn and Kautz networks

0.00 Avg rating0 Votes
Article ID: iaor1993638
Country: Netherlands
Volume: 37/38
Issue: 1/5
Start Page Number: 297
End Page Number: 317
Publication Date: Jul 1992
Journal: Discrete Applied Mathematics
Authors:
Abstract:

The authors prove that, for any equ1, there exists a spanning directed p-ary tree of depth at most equ2in 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 equ3on the broadcast time of these digraphs, which improves the previously known bounds for equ4. 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). The authors obtain several results which are refinements of the following general statements: (i) for any equ5, equ6, if equ7, equ8, (ii) for any equ9, if equ10.

Reviews

Required fields are marked *. Your email address will not be published.