A Better Upper Bound on the Bisection Width of de Bruijn Networks

摘要

We approach the problem of bisectioning the de Bruijn network into two parts of equal size and minimal number of edges connecting the two parts (cross-edges). We introduce a general method that is based on required substrings. A partition is defined by taking as one part all the nodes containing a certain string and as the other part all the other nodes. This leads to good bisections for a large class of dimensions. The analysis of this method for a special kind of substrings enables us to computte for an infinite class of de Bruijn networks a bisection, that has asymptotically only 2 ln(2) 2~n /n cross-edges. This improves previously known bisections with 4 2~n /n cross-edges.