Name
Abstract | ||
|---|---|---|
We show that, with overwhelming probability, several well-known layout problems are approximable within a constant for random graphs drawn from the G(n,pn) model where C/n⩽pn⩽1 for all n big enough and for some properly characterized parameter C>1. In fact, our results establish that, with overwhelming probability, the cost of any arbitrary layout of such a random graph is within a constant of the optimal cost. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0012-365X(00)00278-8 | Discrete Mathematics |
Keywords | Field | DocType |
random graph | Random element,Random regular graph,Discrete mathematics,Combinatorics,Random graph,Optimal cost,Mathematics,Random function | Journal |
Volume | Issue | ISSN |
235 | 1 | 0012-365X |
Citations | PageRank | References |
7 | 0.89 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| Jordi Petit | 2 | 68 | 6.10 |
| Maria Serna | 3 | 216 | 18.19 |
| Luca Trevisan | 4 | 2995 | 232.34 |