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

  • 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 '19 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 '19 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 '19 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 '19 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.