Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?


Yes. Given the adjacency matrix representation of a graph, computing its second power will allow you to see what nodes are connected by a path of length at most 2. The fastest known matrix multiplication algorithm is $O(n^{2.373})$, which is better than the $O(VE)$ you would get from doing BFS on each node.

| cite | improve this answer | |
  • $\begingroup$ Correct in general, but if the graph is sparse--$|E| \in O(|V|)$--then we do better with BFS. $\endgroup$ – Ryan Jun 6 '15 at 18:43
  • $\begingroup$ Also BFS has a worst case complexity $O(|V| + |E|)$. $\endgroup$ – Luke Mathieson Jun 7 '15 at 3:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.