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
Diameter of Tree - can it be done better than in O(V*(V+E))
Moderator: Board moderators
Diameter of Tree - can it be done better than in O(V*(V+E))
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
Problem numbers in uVa
Can someone post problem numbers in the UVA where we need to find the diameter of the graph? ... thanks.
regards,
nymo
nymo
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)
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
Another problem :)
Hi Serur, a straightforward problem of finding the diameter of a tree at UVa is 10308- Roads in the North. Thanks.
regards,
nymo
nymo
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"
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