Deterministic approximation for the cover time of trees

Details Deterministic approximation for the cover time of trees Deterministic approximation for the cover time of trees

2009-09-10

arxiv.org/abs/0909.2005v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present a deterministic algorithm that given a tree T with n vertices, a starting vertex v and a slackness parameter epsilon > 0, estimates within an additive error of epsilon the cover and return time, namely, the expected time it takes a simple random walk that starts at v to visit all vertices of T and return to v. The running time of our algorithm is polynomial in n/epsilon, and hence remains polynomial in n also for epsilon = 1/n^{O(1)}. We also show how the algorithm can be extended to estimate the expected cover (without return) time on trees.

Affiliated with

Also associated with

No associations

Rating

Deterministic approximation for the cover time of trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deterministic approximation for the cover time of trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic approximation for the cover time of trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-132210