DarkSilver's blog

Diameter of a graph?
By DarkSilver, history, 5 weeks ago, In English

While I was trying to solve a problem that given a network of people prove that any two people are separated by a distance of 6 or less. I tried pondering on any sub-quadratic solution by finding maximum shortest distance in a graph. Are there any common know methods to find diameter of graph?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

I'm pretty sure that in general graph you cannot do better than $$$O(N^2)$$$. Someone please correct me if I am wrong.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are right

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please suggest some source to read about it ?

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what source you mean? Source of all type of graph? you can write more detail. if you want know why check diameter have to O(N^2), badly, i dont have any source for that, i just think.

      → Reply