Diameter of Tree - can it be done better than in O(V*(V+E))

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Diameter of Tree - can it be done better than in O(V*(V+E))

Post by serur » Sat Nov 11, 2006 12:11 pm

Hi fellows!

What's the proper approach to finding Diamter of a tree?
Obvious solution: for each vertice do bfs. Is there any other way?
I read about rooting, rootfix and all that kind of thing, but what do you say?

regards,
serur
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Nov 11, 2006 12:27 pm

This can quite easily be done in O(V). Pick a root and start a DFS from it which returns both the diameter of the subtree and its maximum height. The diameter is the maximum of (left diameter, right diameter, left height + right height).

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Sat Nov 11, 2006 12:32 pm

Is this state-of-art solution? I'll try it now...
Well, can this approach solve spoj-problem Labyrinth?...
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Problem numbers in uVa

Post by nymo » Sat Nov 11, 2006 7:00 pm

Can someone post problem numbers in the UVA where we need to find the diameter of the graph? ... thanks.
regards,
nymo

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Thu Nov 16, 2006 7:11 pm

Hi, nymo.

There is a nice problem by Abednego somewhere in 108xx as far as I can remember - about minimum diameter spanning tree. "Labyrinth" from SPOJ is pretty straightforward one.

Well, answering the question posed here -

YES, diameter of a tree can be found in O(V+E)
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Another problem :)

Post by nymo » Mon Nov 20, 2006 12:45 pm

Hi Serur, a straightforward problem of finding the diameter of a tree at UVa is 10308- Roads in the North. Thanks.
regards,
nymo

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue Nov 21, 2006 9:58 am

Hi, felows!

nymo, thank you for a nice problem. So for an arbitrary tree diameter problem can be solved in O(V+E), i.e. with constant number of bfs's. My question here is: now please you fellows comment here on minimum-diameter spanning tree problem.

EDIT: to nymo:
problems about diameter of tree from Sphere Online judge:
- "Labyr1"
- "Benefact"
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Post Reply

Return to “Algorithms”