5
$\begingroup$

Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?

$\endgroup$
  • 3
    $\begingroup$ Currently the fastest deterministic algorithm for diameter in general should be Chan-Williams which runs in $n^3/2^{\Omega(\sqrt{\log n})}$ time, matching the previous randomized algorithm by Williams. But there are better algorithms when the graph is special, or if you accept approximated solutions. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 21 at 17:54
  • 3
    $\begingroup$ I guess the OP could've searched a little more to find the answer to his question, but I am still surprised this question is getting buried so much $\endgroup$ – Sasho Nikolov Jan 22 at 1:16
  • 3
    $\begingroup$ I think there's interesting, recent literature on this question besides the fast algorithms for APSP that Hsien-Chih mentions. I.e., see people.csail.mit.edu/virgi/diam.pdf which gives approximation algorithms and fine-grained complexity results. $\endgroup$ – Huck Bennett Jan 22 at 1:44
  • 3
    $\begingroup$ @Hsien-ChihChang張顯之, HuckBennett, these comments seem like reasonable answers to the question, would you consider posting them as answers? $\endgroup$ – a3nm Jan 22 at 10:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.