Timeline for diameter of a graph with random edge weights
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2010 at 5:42 | comment | added | Tom LaGatta | Oops, you're absolutely right. It should be the opposite of what I said: the diameter should cluster on small values. Say you want to connect x to y. There's the one-edge path which connects them, and there are O(|G|) two-edge paths. There is a very high chance that one of them will have a very small weight. | |
| Jun 16, 2010 at 5:25 | comment | added | alex | Thanks for the references; will check them out. In the very connected case, my intuition says that the opposite of your statement is true: even if one $w_{ij}$ is large, the existence of many paths between any two vertices will insure that the diameter is not strongly affected. | |
| Jun 16, 2010 at 5:18 | history | answered | Tom LaGatta | CC BY-SA 2.5 |