The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems)
Juraj Hromkovic̆, Burkhard Monien · Teubner-Texte zur Informatik · 1992
It is well-known that for each k ≥ 3 there exists a constant c k and an infinite sequence \( \left\{ {{G_n}} \right\}_n^\infty = 8 \) of k-degree graphs (each G n has exactly n vertices) that the bisection width of G n is at least c k • n. It this paper some upper bounds on the c k ′s are found. Let σ k (n) be the maximum of bisection widths of all k-degree graphs of n vertices. We prove that $${\sigma _k}\left( n \right) \leqslant \frac{{\left( {k - 2} \right)}}{4} \cdot n + O\left( {\sqrt n } \right) $$ for all even k. This result is improved for k = 4 by constructing two algorithms A and B, where for a given 4-degree graph G n of n vertices(i) A constructs a bisection of G n involving at most n/2 + 4 edges for even n ≤ 60 (i.e., σ4(n) 350). The algorithms A and B run in O(n 2 ) time on graphs of n vertices, and they are used to optimize hardware for building large transputer systems.