Name
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. 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≤d≤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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2007.03.003 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
bisection width,random regular graphs | Journal | 382 |
Issue | ISSN | Citations |
2 | 0304-3975 | 15 |
PageRank | References | Authors |
0.88 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 65 | 7.03 |
| Maria J. Serna | 2 | 473 | 70.53 |
| Nicholas C. Wormald | 3 | 1506 | 230.43 |