farthest from 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1.
won't v2 be farthest from r? or we are talking about alternate pats also Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, Jun 20, 2012 at 6:25 PM, adarsh kumar <algog...@gmail.com> wrote: > As you traverse along and find the diameter of the tree, keep track of the > number of nodes thereby traversed. Let that be equal to n. > Now, centre is the node corresponding to floor((n+1)/2). > > > On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey < > nishant.bits.me...@gmail.com> wrote: > >> I am asking again .. can any one please suggest better method for getting >> the median on the longest path of the tree .. >> efficient method . >> >> >> On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey < >> nishant.bits.me...@gmail.com> wrote: >> >>> >>> for getting diameter we can simply add the max height of left subtree >>> and max height of the right sub tree . >>> >>> the main issue is how efficiently we find median on that longest path to >>> get the center of the tree . >>> can any bdy sugest optimized algo for that ? >>> >>> >>> On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey < >>> rajesh.pandey.i...@gmail.com> wrote: >>> >>>> I found it in some paper ;) >>>> >>>> Diameter and center >>>> De nition 4. The diameter of tree is the length of the longest path. >>>> De nition 5. A center is a vertex v such that the longest path from v >>>> to a leaf is minimal >>>> over all vertices in the tree.Tree center(s) can be found using simple >>>> algorithm. >>>> Algorithm 1. (Centers of tree) >>>> 1: Choose a random root r. >>>> 2: Find a vertex v1 | the farthest form r. >>>> 3: Find a vertex v2 | the farthest form v1. >>>> 4: Diameter is a length of path from v1 to v2. >>>> 5: Center is a median element(s) of path from v1 to v2. >>>> >>>> This is O(n) algorithm. It is clear that we can't determine tree >>>> isomorphism faster >>>> than O(n). So, if we nd a O(f(n)) algorithm for rooted trees >>>> isomorphism we can also >>>> obtain O(f(n)) algorithm for ordinary trees. >>>> >>>> On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: >>>>> >>>>> I think this algorithm is used for calculating poset in graph. >>>>> >>>>> On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh >>>>> <hemesh.mn...@gmail.com>wrote: >>>>> >>>>>> + 1 for DK's solution. Is that a standard algorithm coz I feel like I >>>>>> have heard it somewhere ?? >>>>>> >>>>>> >>>>>> On Mon, Aug 8, 2011 at 1:37 AM, DK <divyekap...@gmail.com> wrote: >>>>>> >>>>>>> @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). >>>>>>> Could you please state how you can use the traversals directly to >>>>>>> get the center? (And prove your correctness too?) >>>>>>> >>>>>>> The solution given by Wladimir (& expanded upon by me) is O(N) and >>>>>>> uses (somewhat) the inverse of a BFS as a traversal. >>>>>>> >>>>>>> -- >>>>>>> DK >>>>>>> >>>>>>> http://twitter.com/divyekapoor >>>>>>> http://gplus.to/divyekapoor >>>>>>> http://www.divye.in >>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "Algorithm Geeks" group. >>>>>>> To view this discussion on the web visit >>>>>>> https://groups.google.com/d/**msg/algogeeks/-/HnMOZtOrkqwJ<https://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ>. >>>>>>> >>>>>>> >>>>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@ >>>>>>> **googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>>>>> For more options, visit this group at http://groups.google.com/** >>>>>>> group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>>> . >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Hemesh singh >>>>>> >>>>>> -- >>>>>> 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 algogeeks+unsubscribe@* >>>>>> *googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>>>> For more options, visit this group at http://groups.google.com/** >>>>>> group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>> . >>>>>> >>>>> >>>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. >>>> >>>> To post to this group, send email to algogeeks@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. >>>> >>> >>> >>> >>> -- >>> Cheers, >>> >>> Nishant Pandey |Specialist Tools Development | >>> npan...@google.com<gvib...@google.com> | >>> +91-9911258345 >>> >>> >>> >> >> >> -- >> Cheers, >> >> Nishant Pandey |Specialist Tools Development | >> npan...@google.com<gvib...@google.com> | >> +91-9911258345 >> >> >> -- >> 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 >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
