Bounds on the max and min bisection of random cubic and random 4-regular graphs

J. Díaz, N. Do, M. J. Serna, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

15 Citations (Scopus)

Abstract

In this paper, we present a randomized algorithm to compute the bisection width of cubic and 4-regular graphs. The analysis of the proposed algorithms on random graphs provides asymptotic upper bounds for the bisection width of random cubic and random 4-regular graphs with n vertices, giving upper bounds of 0.174039n for random cubic, and of 0.333333n for random 4-regular. We also obtain asymptotic lower bounds for the size of the maximum bisection, for random cubic and random 4-regular graphs with n vertices, of 1.32697n and 1.66667n, respectively. The randomized algorithms are derived from initial greedy algorithm and their analysis is based on the differential equation method.

Original languageEnglish
Pages (from-to)531-547
Number of pages17
JournalTheoretical Computer Science
Volume307
Issue number3
DOIs
Publication statusPublished - 14 Oct 2003
Externally publishedYes

Keywords

  • Bisection width
  • Random 4-regular graphs
  • Random cubic graphs

Cite this