\input zb-basic
\input zb-ioport
\iteman{io-port 05191641}
\itemau{D{\'\i}az, J.; Serna, M.J.; Wormald, N.C.}
\itemti{Bounds on the bisection width for random $d$-regular graphs.}
\itemso{Theor. Comput. Sci. 382, No. 2, 120-130 (2007).}
\itemab
Summary: We provide an explicit way to compute asymptotically almost sure upper bounds on the bisection width of random $d$-regular graphs, for any value of $d$. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of $d$-regular graphs. We provide bounds for $5 \leq d \leq 12$. We also give empirical values of the size of the bisection found by the algorithm for some small values of $d$ and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum bisection.
\itemrv{~}
\itemcc{}
\itemut{Bisection width; random regular graphs}
\itemli{doi:10.1016/j.tcs.2007.03.003}
\end