Computation of the bisection width for random d-regular graphs

Josep Díaz, Maria J. Serna, Nicholas C. Wormald

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)


In this paper 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. We provide the bounds for 5 ≤ d ≤ 12. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of d-regular graphs. We also give empirical values of the size of bisection found by the algorithm for some small values of d and compare it with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum bisection.

Original languageEnglish
Title of host publicationLATIN 2004: Theoretical Informatics
Subtitle of host publication6th Latin American Symposium Buenos Aires, Argentina, April 5-8, 2004 Proceedings
EditorsMartin Farach-Colton
Place of PublicationBerlin Germany
Number of pages10
ISBN (Print)3540212582
Publication statusPublished - 2004
Externally publishedYes
EventInternational Symposium on Latin American Theoretical Informatics 2004 - Buenos Aires, Argentina
Duration: 5 Apr 20048 Apr 2004
Conference number: 6th (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Symposium on Latin American Theoretical Informatics 2004
Abbreviated titleLATIN 2004
CityBuenos Aires
Internet address

Cite this