Cover Time for Random Walks on Graphs |
| 09.12.2019, 15:30 | ueberdeckungszeit | Auf diesen Beitrag antworten » |
| Cover Time for Random Walks on Graphs Kann mir jemand helfen den Beweis von Lemma 8 in Uriel Feige's Paper "A tight lower bound on the cover time for random walks on graphs" zu verstehen? Insbesondere verstehe ich nicht, wie man die untere Schranke D[v_{i_j},v_{i_{j+1}}]?n \log^2 n findet? Meine Ideen: Da wir annehmen, dass der zweite Fall nicht gilt, habe ich versucht herauszufinden was das für S bedeutet aber bin nicht wirklich damit weiter gekommen. Auch mit der Additivitätseigenschaft von D ist es mir nicht gelungen die Schranke zu finden. Hoffentlich kann mir hier jemand weiterhelfen? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
