Examples for directed graphs with super polynomial cover time
-
01-11-2019 - |
Pregunta
The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes.
For undirected graphs the cover time is upperbounded by $O(n^3)$. What about directed graphs? I'm looking for examples of super-polynomial cover time.
Is there an example for such graph with $O(2^{\sqrt n})$ cover time?
No hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange