Timeline for Good algorithm for finding the diameter of a (sparse) graph?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2010 at 0:58 | comment | added | Mariano Suárez-Álvarez | Well, I more or less doubt one can compute the diameter without doing work equivalent to computing all shortests paths... | |
| Jan 11, 2010 at 17:11 | comment | added | aorq | I asked if there was a better approach than computing all-pairs shortest paths. Johnson's algorithm computes all-pairs shortest paths by running Dijkstra for each vertex (after a preprocessing step take makes weights non-negative). | |
| Jan 11, 2010 at 16:49 | history | answered | Mariano Suárez-Álvarez | CC BY-SA 2.5 |