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

CC BY-SA 4.0
2019-01-21T17:54:17.340Z
Currently the fastest deterministic algorithm for diameter in general should be [Chan-Williams](http://tmc.web.engr.illinois.edu/detapsp_soda.pdf) which runs in $n^3/2^{\Omega(\sqrt{\log n})}$ time, matching the [previous randomized algorithm](https://arxiv.org/abs/1312.6680) by Williams.  But there are better algorithms when the graph is special, or if you accept approximated solutions.
Hsien-Chih Chang 張顯之
CC BY-SA 4.0
2019-01-22T01:16:37.423Z
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
Sasho Nikolov
CC BY-SA 4.0
2019-01-22T01:44:15.193Z
I think there's interesting, recent literature on this question besides the fast algorithms for APSP that Hsien-Chih mentions. I.e., see https://people.csail.mit.edu/virgi/diam.pdf which gives approximation algorithms and fine-grained complexity results.
Huck Bennett
CC BY-SA 4.0
2019-01-22T10:42:13.353Z
@Hsien-ChihChang張顯之, HuckBennett, these comments seem like reasonable answers to the question, would you consider posting them as answers?
Antoine Amarilli 'a3nm'
<ds.algorithms><graph-theory>
What's the fastest known algorithm for finding the diameter of a graph?
GEP
# What's the fastest known algorithm for finding the diameter of a graph?

(Asked by: username_0 on 2019-01-21)

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

**Tags:** ds.algorithms, graph-theory

> **Comments:**
> **username_1**: Currently the fastest deterministic algorithm for diameter in general should be [Chan-Williams](http://tmc.web.engr.illinois.edu/detapsp_soda.pdf) which runs in $n^3/2^{\Omega(\sqrt{\log n})}$ time, matching the [previous randomized algorithm](https://arxiv.org/abs/1312.6680) by Williams.  But there are better algorithms when the graph is special, or if you accept approximated solutions.  
> **username_2**: 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  
> **username_3**: I think there's interesting, recent literature on this question besides the fast algorithms for APSP that Hsien-Chih mentions. I.e., see https://people.csail.mit.edu/virgi/diam.pdf which gives approximation algorithms and fine-grained complexity results.  
> **username_4**: @Hsien-ChihChang張顯之, HuckBennett, these comments seem like reasonable answers to the question, would you consider posting them as answers?  

---

## 0 answers

