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.
