ALCOMFT-TR-02-102

J. D\'\iaz, N. Do, M. J. Serna and N. C. Wormald
Bisection of Random Cubic Graphs
Barcelona. Work package 4. May 2002.

Abstract: In this paper we present two randomized algorithms to compute the bisection width of random cubic graphs with n vertices, giving an asymptotic upper bound for the bisection width respectively of 0.174039n and 0.174501n. We also obtain an asymptotic lower bound for the size of the max bisection of a random cubic graph with n vertices of 1.325961n and 1.325499n. The analysis is based on the differential equation method.

Postscript file: ALCOMFT-TR-02-102.ps.gz (100 kb).