Timeline for Uniform sampling of random connected graph with given number of vertices/edges
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2018 at 9:43 | comment | added | j.c. | There's a suggestion by Yuval Filmus here cs.stackexchange.com/questions/71943/… in the small $m$ case to modify uniform spanning trees generated by e.g. Wilson's algorithm by adding edges. | |
| Apr 9, 2018 at 2:02 | answer | added | Brendan McKay | timeline score: 5 | |
| Apr 9, 2018 at 0:29 | comment | added | Brendan McKay | @usul : OP is only saying that it is uniform for fixed $n,m$. Actually using $G_{n,m}$ would be better than using $G_{n,p}$. | |
| Apr 8, 2018 at 23:50 | comment | added | usul | "If the density (i.e. m) is sufficiently high, then an Erdős-Rényi graph will be connected with relatively high probability. Thus we can generate such random graphs and reject any that are not connected." I don't see that this would be uniform (consider $p=0.99$ versus $p=0.01$). | |
| Apr 8, 2018 at 22:18 | comment | added | Max Alekseyev | Just an idea - instead of adding edges to the empty graph, remove them from the complete graph in random order, skipping removal if it destroys graph connectivity. | |
| Apr 8, 2018 at 17:24 | history | undeleted | Szabolcs Horvát | ||
| Apr 8, 2018 at 17:19 | history | deleted | Szabolcs Horvát | via Vote | |
| Apr 8, 2018 at 17:15 | history | edited | Szabolcs Horvát | CC BY-SA 3.0 |
added 127 characters in body
|
| Apr 8, 2018 at 17:00 | history | asked | Szabolcs Horvát | CC BY-SA 3.0 |