Computation of the bisection width for random d-regular graphs

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

doi:10.1007/978-3-540-24698-5_9

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 proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

Abstract

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 language	English
Title of host publication	LATIN 2004: Theoretical Informatics
Subtitle of host publication	6th Latin American Symposium Buenos Aires, Argentina, April 5-8, 2004 Proceedings
Editors	Martin Farach-Colton
Place of Publication	Berlin Germany
Publisher	Springer
Pages	49-58
Number of pages	10
ISBN (Print)	3540212582
DOIs	https://doi.org/10.1007/978-3-540-24698-5_9
Publication status	Published - 2004
Externally published	Yes
Event	International Symposium on Latin American Theoretical Informatics 2004 - Buenos Aires, Argentina Duration: 5 Apr 2004 → 8 Apr 2004 Conference number: 6th https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b95852 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2976
ISSN (Print)	0302-9743

Conference

Conference	International Symposium on Latin American Theoretical Informatics 2004
Abbreviated title	LATIN 2004
Country/Territory	Argentina
City	Buenos Aires
Period	5/04/04 → 8/04/04
Internet address	https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b95852 (Proceedings)

Access to Document

10.1007/978-3-540-24698-5_9

Cite this

Díaz, J., Serna, M. J., & Wormald, N. C. (2004). Computation of the bisection width for random d-regular graphs. In M. Farach-Colton (Ed.), LATIN 2004: Theoretical Informatics: 6th Latin American Symposium Buenos Aires, Argentina, April 5-8, 2004 Proceedings (pp. 49-58). (Lecture Notes in Computer Science; Vol. 2976). Springer. https://doi.org/10.1007/978-3-540-24698-5_9

@inproceedings{fbf9d5d8044d4522a807d31bfbf01453,

title = "Computation of the bisection width for random d-regular graphs",

abstract = "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.",

author = "Josep D{\'i}az and Serna, {Maria J.} and Wormald, {Nicholas C.}",

year = "2004",

doi = "10.1007/978-3-540-24698-5_9",

language = "English",

isbn = "3540212582",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "49--58",

editor = "Martin Farach-Colton",

booktitle = "LATIN 2004: Theoretical Informatics",

note = "International Symposium on Latin American Theoretical Informatics 2004, LATIN 2004 ; Conference date: 05-04-2004 Through 08-04-2004",

url = "https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b95852",

}

Díaz, J, Serna, MJ & Wormald, NC 2004, Computation of the bisection width for random d-regular graphs. in M Farach-Colton (ed.), LATIN 2004: Theoretical Informatics: 6th Latin American Symposium Buenos Aires, Argentina, April 5-8, 2004 Proceedings. Lecture Notes in Computer Science, vol. 2976, Springer, Berlin Germany, pp. 49-58, International Symposium on Latin American Theoretical Informatics 2004, Buenos Aires, Argentina, 5/04/04. https://doi.org/10.1007/978-3-540-24698-5_9

Computation of the bisection width for random d-regular graphs. / Díaz, Josep; Serna, Maria J.; Wormald, Nicholas C.

LATIN 2004: Theoretical Informatics: 6th Latin American Symposium Buenos Aires, Argentina, April 5-8, 2004 Proceedings. ed. / Martin Farach-Colton. Berlin Germany : Springer, 2004. p. 49-58 (Lecture Notes in Computer Science; Vol. 2976).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Computation of the bisection width for random d-regular graphs

AU - Díaz, Josep

AU - Serna, Maria J.

AU - Wormald, Nicholas C.

N1 - Conference code: 6th

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35048834237&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24698-5_9

DO - 10.1007/978-3-540-24698-5_9

M3 - Conference Paper

AN - SCOPUS:35048834237

SN - 3540212582

T3 - Lecture Notes in Computer Science

SP - 49

EP - 58

BT - LATIN 2004: Theoretical Informatics

A2 - Farach-Colton, Martin

PB - Springer

CY - Berlin Germany

T2 - International Symposium on Latin American Theoretical Informatics 2004

Y2 - 5 April 2004 through 8 April 2004

ER -

Computation of the bisection width for random d-regular graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this