𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bisecting de Bruijn and Kautz graphs

✍ Scribed by José Rolim; Pavel Tvrdik; Jan Trdlička; Imrich Vrto

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
675 KB
Volume
85
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

De Bruijn and Kautz graphs have been intensively studied as perspective interconnection networks of massively parallel computers. One of the crucial parameters of an interconnection network is its bisection width. It has an influence on both communication properties of the network and the algorithmic design. We prove optimal bounds on the edge and vertex bisection widths of the k-ary n-dimensional de Bruijn digraph. This generalizes known results for k = 2 and improves the upper bound for the vertex bisection width. We extend the method to prove optimal upper and lower bounds on the edge and vertex bisection widths of Kautz graphs.

📜 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

Superfluous edges and exponential expans
Superfluous edges and exponential expansions of De Bruijn and Kautz graphs
✍ Eduardo A. Canale; José Gómez 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 644 KB

A new way to expand De Bruijn and Kautz graphs is presented. It consists of deleting super uous sets of edges (i.e., those whose removal does not increase the diameter) and adding new vertices and new edges preserving the maximum degree and the diameter. The number of vertices added to the Kautz gra

De Bruijn and Kautz bus networks
De Bruijn and Kautz bus networks
✍ Bermond, Jean-Claude; Dawes, Robin W.; Ergincan, Fahir �. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 598 KB

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

Embedding de Bruijn, Kautz and shuffle-e
Embedding de Bruijn, Kautz and shuffle-exchange networks in books
✍ Toru Hasunuma; Yukio Shibata 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 839 KB

We show that the de Bruijn digraph B(d,D), D > 1 and the Kautz digraph K(d,D) can be embedded in (d + 1) pages with cumulative pagewidth ~dDe2(3d3 -2d2 + 4d -d(d mod 2) ~ 4) and idD-'(3d' + 4d + (d mod2)), respectively. Also we show that the shuffle-exchange graph S(D; D > 2 can be embedded in 3 pag