Skip to main content
7 of 9
deleted 35 characters in body
JeffE
  • 8.8k
  • 1
  • 36
  • 47

The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$?

  • ${O}(|V|^2)$
  • ${O}(|V|^2+|V| \cdot |E|)$
  • ${O}(|V|^2\cdot |E|)$
  • ${O}(|V|\cdot |E|^2)$

The diameter of a graph $G$ is the longest distance between two vertices in graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.

Gigili
  • 2.2k
  • 3
  • 21
  • 31