Timeline for Cover time of weighted graphs
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2010 at 23:36 | comment | added | Emil | So the question now seems to be: does the conditions on the weights given in the first paragraph cause the cover time to be $O(n^2\log n)$, rather than merely $O(n^3)$? | |
| Jul 23, 2010 at 17:05 | comment | added | James Martin | what "bound" are you talking about, Suresh? There are certainly examples of families of weighted graphs where the cover time is of larger order than $n^3$, and there are certainly examples (like the one I described) where the cover time is of smaller order than $n^3$. | |
| Jul 23, 2010 at 10:04 | comment | added | MAKCL | btw Suresh, $O(n^2)$ max hitting time implies $O(n^2\log n)$ cover time by Matthews' technique. | |
| Jul 23, 2010 at 9:40 | comment | added | MAKCL | James, thanks for your answer. This is the problem with asking these types of questions on the net. I have a certain set of constraints in mind, that your example would violate, but the more specific I get about the problem, the less it becomes mine to solve, if you know what I mean. As a consequence, I don't really think through the implications of relaxing (ie not mentioning) those constraints. It's ok though, I think I might have an idea. | |
| Jul 23, 2010 at 8:28 | comment | added | Suresh Venkat | in fact the dumbell graph (two cliques of size n connected by a path of length n) give the $n^3$ bound. | |
| Jul 23, 2010 at 8:26 | history | answered | James Martin | CC BY-SA 2.5 |