Timeline for Good algorithm for finding the diameter of a (sparse) graph?
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| May 28, 2013 at 5:17 | answer | added | Urakov | timeline score: 2 | |
| Feb 11, 2013 at 14:15 | answer | added | Andrea Marino | timeline score: 5 | |
| Apr 17, 2011 at 13:09 | answer | added | trg787 | timeline score: -2 | |
| Dec 6, 2010 at 21:04 | comment | added | Lucas K. | I just wonder. If the graph is a tree, then there is a simple trick. Just, start with a point, find the point furthest away. Then search the point furthest away from that point. Then you have the longest path (or one of them, in case of multiple solutions). Suppose you apply the same method on a graph, instead of tree. The points on the paths already found, can not be the end points of such longest path. So, you skip them as potential candidates. You repeat this, until all points have been tried. Could this work? | |
| Dec 6, 2010 at 20:18 | vote | accept | aorq | ||
| Dec 6, 2010 at 20:03 | answer | added | David Eppstein | timeline score: 9 | |
| Jan 13, 2010 at 1:45 | comment | added | Ryan Williams | Do you need the exact diameter, or would approximate methods suffice? (I have the suspicion that an exact "truly subcubic" diameter finding algorithm would yield a subcubic all-pairs shortest paths algorithm on unweighted graphs. But note, the latter can be theoretically solved in matrix multiplication time...) | |
| Jan 12, 2010 at 1:43 | answer | added | Wilson | timeline score: 1 | |
| Jan 11, 2010 at 17:17 | comment | added | aorq | @Steve: Thanks for the reference. Their "matrix methods" section essentially runs the Bellman–Ford algorithm in time O(V^3). Their "non-matrix methods" sections runs Dijktra for each vertex, which is Johnson's algorithm at O(V^2 log V + VE). However, they combine this with an upper bound for the diameter, obtained from the diameter of the minimum spanning tree (which can be computed quite efficiently). Unfortunately, if their bound is not met (and they have no reason to believe it will be), their suggestion is simply Johnson's algorithm for all-pairs shortest paths. | |
| Jan 11, 2010 at 16:49 | answer | added | Mariano Suárez-Álvarez | timeline score: 1 | |
| Jan 11, 2010 at 16:49 | comment | added | Steve Huntsman | See the "non-matrix methods" section of sawww.epfl.ch/SIC/SA/publications/SCR98/scr10-page3.html | |
| Jan 11, 2010 at 16:36 | history | asked | aorq | CC BY-SA 2.5 |