title: Random walks on networks: cumulative distribution of cover time.
abstract: We derive an exact closed-form analytical expression for the distribution of the cover time for a random walk over an arbitrary graph. In special case, we derive simplified exact expressions for the distributions of cover time for a complete graph, a cycle graph, and a path graph. An accurate approximation for the cover time distribution, with computational complexity of O(2n) , is also presented. The approximation is numerically tested only for graphs with n<or=1000 nodes.
authors.affiliation: Macedonian Academy for Sciences and Arts, 1000 Skopje, Republic of Macedonia.
authors.forename: Nikola
authors.initials: N
authors.lastname: Zlatanov
authors.forename: Ljupco
authors.initials: L
authors.lastname: Kocarev
mesh_terms: D000465:Algorithms; D011336:Probability; D013269:Stochastic Processes; D013997:Time Factors