Calculate center of a tree, can be solved in O(n). On 10/25/07, dkrai <[EMAIL PROTECTED]> wrote: > > > Another approach can be to eliminate leaf nodes iteratively from tree. > At last only root node or nodes on same level will be left. > > Adjency list representation of graph will make it easier to > imlplement. > Run time cost will be O(n*n) > > On Oct 24, 12:37 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> > wrote: > > Two methods: > > 1. try BFS on each vertex, calculate the longest shortest path to > > each other vertex, compare them > > It is easy to implement, but gives O(n*n) running time > > > > 2. divide and conquer > > randomly divide the tree into two parts, calculate the height of > > the two subtrees then merge them. > > This is not so easy to implement, but really gives a good running > > time which is O(nlogn) > > > > On Oct 21, 9:21 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > > > > > > > > > Q) You are given a root-less tree (which can also be thought of as an > > > undirected acyclic connected graph). The problem is to choose one of > > > the nodes from the tree as root such that the height of the resultant > > > tree is minimum. > > > > > Device an appropriate data-structure and write a program for the > > > same. > > > mum height possible is 2. So for this example the code should return > > > the node '3'. > > > > > Note: All nodes are numbered from 1 to n, where 'n' is the number of > > > nodes. Incase there are more than one roots possible, then your > > > program can return any one of them.- Hide quoted text - > > > > - Show quoted text - > > > > >
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
