The bisection width and the isoperimetric number of arrays. (Q1428547): Difference between revisions

A \(d\)-dimensional array \(A^d\) is a graph with \(k_1\times \cdots\times k_d\) vertices, \(k_i<k_{i+1}\), each having a unique label \(l=(l_1,\dots,l_d)\), where \(0<l_i <k_{i-1}\). There is an edge between two vertices if their labels differ in exactly one dimension and the difference is exactly one. The authors prove that the bisection width bw\((A^d)\) is given by \( \text{bw}(A^d)= \sum^d_{i=e}K_i\), where \(e\) is the largest index for which \(k_e\) is even (if it exists, \(e=1\) otherwise) and \(K_i=k_{i-1}\) of \(k_{i-2}\cdots k_1\). They also show that the edge-isoperimetric number \(i(A^d)\) is given by \(i(A^d)=1/[k_d/2]\), where \([a]\) is the integral part \(a\).