0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Correct in general, but if the graph is sparse--$|E| \in O(|V|)$--then we do better with BFS. $\endgroup$ Commented Jun 6, 2015 at 18:43
  • $\begingroup$ Also BFS has a worst case complexity $O(|V| + |E|)$. $\endgroup$ Commented Jun 7, 2015 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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