Name
Abstract | ||
|---|---|---|
We consider arbitrary graphs G with n vertices and minimum degree at least delta n where delta > 0 is constant. (a) If the conductance of G is sufficiently large, then we obtain an asymptotic expression for the cover time C-G of G as the solution to an explicit transcendental equation. (b) If the conductance is not large enough to apply (a), but the mixing time of a random walk on G is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense subgraphs with high conductance. (c) If G fits neither (a) nor (b), then we give a deterministic asymptotic (2+o(1))-approximation of C-G. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/18M122039X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
cover time,dense graphs,deterministic algorithm | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Deterministic algorithm,Conductance,Mathematics | Journal |
Volume | Issue | ISSN |
33 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 857 | 91.88 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| wesley pegden | 3 | 30 | 11.07 |