I don't understand what you mean when you say "minimum among all the nodes in the graph".
In any case, your definition of centre of tree looks similar to the closeness centrality measure - http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html#Closeness I doubt you can do it in O(N)... On Sep 29, 12:41 pm, jayapriya surendran <priya7...@gmail.com> wrote: > In graph theory, a tree is defined as a graph on N nodes,and (N-1) > un-directed edges such that there are no cycles in the graph.Each node > has a single unique path to every other node. > Let D(u,v) be the number of edges in the unique path from node 'u' to > node 'v' (or from node 'v' to 'u' since the edges are > un-directed).D(u,u) is 0 for all nodes 'u'. > M(u)=MAX(D(u,i):for all nodes i) > The center of a tree is the node (or nodes) 'u',for which M(u) is > minimum among all the nodes in the graph. > You'll be given a graph which has N nodes (1<=N<=20).The nodes are > labeled 1,2,3,..N.You will be provided with N-1 edges in the form of > "a b" pairs where 1<=a,b<=N.No edge will be repeated.You can assume > that the edges are specified such that the graph is a valid tree as > defined above. > Output the node labels of the center(or centers) of the tree. > Sample Input: > 6(value of N) > 1 3 (edges) > 1 4 > 1 2 > 2 5 > 2 6 > > Sample Output > 1 > 2 > Expected:O(N) complexity algo > can anyone plz help me out with O(N) algo? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
