Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

How can I prove that the cover time for a directed graph G can be exponential in the size of G?

share|improve this question
3  
What is the "cover time"? – Raphael♦ Jun 22 '12 at 14:57
I think cover time means the expected number of steps taken by a random walk to visit every vertex. – Juho Jun 22 '12 at 21:19
You also have to assume that the graph is strongly connected. – Yuval Filmus Jan 27 at 6:38

1 Answer

up vote 4 down vote

You do it in two steps:

  1. First you think of a graph which you can expect to be difficult.

  2. Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.