𝔖 Bobbio Scriptorium
✦   LIBER   ✦

De Bruijn and Kautz bus networks

✍ Scribed by Bermond, Jean-Claude; Dawes, Robin W.; Ergincan, Fahir �.

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
598 KB
Volume
30
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Our aim was to find bus interconnection networks which connect as many processors as possible, for given upper bounds on the number of connections per processor, the number of processors per bus, and the network diameter. Point-to-point networks are a special case of bus networks in which every bus connects only two processors. In this case, de Bruijn and Kautz networks and their generalizations are known to be among the best families of networks with respect to the aforementioned criteria. In this paper, we present the directed de Bruijn bus networks, which connect two or more processors on a bus and contain the point-to-point de Bruijn networks and their generalization as a special case. We study two different schemes of the directed de Bruijn bus networks. We also show that the directed Kautz bus networks can be defined in the same manner.

📜 SIMILAR VOLUMES

The Spectrum of de Bruijn and Kautz Grap
The Spectrum of de Bruijn and Kautz Graphs
✍ C. Delorme; J.-P. Tillich 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 187 KB

We give here a complete description of the spectrum of de Bruijn and Kautz graphs. It is well known that spectral techniques have proved to be very useful tools to study graphs, and we give some examples of application of our result, by deriving tight bounds on the expansion parameters of those grap

On even factorizations and the chromatic
On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs
✍ Jean-Claude Bermond Cnrs; Pavol Hell 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB

## Abstract Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in‐ and outdegree __d__ have arc‐chromatic index __2d__. In order to do this, we introduce the concept of even 1‐factorizations. An even 1‐factor of a digraph is a spann

Mean eccentricities of de Bruijn network
Mean eccentricities of de Bruijn networks
✍ Bermond, Jean-Claude; Liu, Zhen; Syska, Michel 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

Given a graph G Å (V, E), we define eV ( X ), the mean eccentricity of a vertex X, as the average distance from X to all the other vertices of the graph. The computation of this parameter appears to be nontrivial in the case of the de Bruijn networks. In this paper, we consider upper and lower bound

Shortest path routing and fault-tolerant
Shortest path routing and fault-tolerant routing on de Bruijn networks
✍ Mao, Jyh-Wen; Yang, Chang-Biau 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB 👁 1 views

In this paper, we study the routing problem for the undirected binary de Bruijn interconnection network. Researchers have never proposed a shortest path routing algorithm on the undirected binary de Bruijn network. We first propose a shortest path routing algorithm, whose time complexity in the bina

2-diameter of de Bruijn graphs
2-diameter of de Bruijn graphs
✍ Li, Qiao; Sotteau, Dominique; Xu, Junming 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 589 KB

This paper shows that in the undirected binary de Bruijn graph of dimension n . UB(n), which has diameter n , there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2-diameter of U B ( n ) is equal to its diameter n .