Name
Abstract | ||
|---|---|---|
We present two randomized algorithms to bound the bisection width of random n-vertex cubic graphs. We obtain an asymptotic upper bound for the bisection width of 0.174039n and a corresponding lower bound
of 1.325961n. The analysis is based on the differential equation method.
|
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45726-7_10 | RANDOM |
Keywords | Field | DocType |
random cubic graphs,lower bound,randomized algorithm,differential equation,cubic graph,upper bound | Differential equation,Randomized algorithm,Discrete mathematics,Combinatorics,Random graph,Bisection,Upper and lower bounds,Hamiltonian path,Cubic graph,Random geometric graph,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-44147-6 | 4 | 0.49 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| N. Do | 2 | 4 | 0.49 |
| Maria J. Serna | 3 | 473 | 70.53 |
| Nicholas C. Wormald | 4 | 1506 | 230.43 |