Cover Time for Random Walks on Graphs

Neue Frage »

ueberdeckungszeit Auf diesen Beitrag antworten »
Cover Time for Random Walks on Graphs
Meine Frage:
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?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »