Timeline for Estimate size of graph by taking random walks
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17, 2013 at 17:29 | comment | added | Neal Young | sciencedirect.com/science/article/pii/S0022000097915348 "Size-estimation framework with applications to transitive closure and reachability" | |
| Aug 16, 2013 at 18:34 | answer | added | Vincent Beffara | timeline score: 1 | |
| Aug 16, 2013 at 17:41 | answer | added | The Masked Avenger | timeline score: 1 | |
| Aug 16, 2013 at 16:26 | comment | added | usul | @Tino, ok, but if you are visiting $o(n)$ vertices and making $o(n)$ modifications (where $n$ is the number of vertices), it still seems very unlikely to me. | |
| Aug 16, 2013 at 5:37 | comment | added | tuna | @usul: Remember that we can modify the graph locally, for example by deleting vertices we've visited. | |
| Aug 16, 2013 at 1:39 | comment | added | usul | I'd guess that what you're asking is too difficult, unless we have a DAG. One intuition is that, if we cannot remember which vertices we've visited, then it will be difficult to distinguish between a small cycle and a very long line. | |
| Aug 16, 2013 at 0:33 | comment | added | tuna | @Anton: I guess those are local modifications! But I'm looking for a method that will work when $G$ is too big to do, say, a number of operations as large as the number of vertices of $G$. | |
| Aug 16, 2013 at 0:28 | review | First posts | |||
| Aug 16, 2013 at 0:33 | |||||
| Aug 16, 2013 at 0:21 | comment | added | Anton Petrunin | Move from $v_0$ to $v_1$, remove $v_0$ and connect all the vertices which were connected to $v_0$ by edges; move from $v_1$ to $v_2$ and so on as far as you can walk. The number of steps gives you the number of vertices in a connected graph. | |
| Aug 16, 2013 at 0:08 | history | asked | tuna | CC BY-SA 3.0 |