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 <[email protected] > 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 <[email protected]>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 <[email protected]> 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 [email protected]. >>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>>> googlegroups.com <algogeeks%[email protected]>. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>> googlegroups.com <algogeeks%[email protected]>. >>> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Cheers, Nishant Pandey |Specialist Tools Development | [email protected]<[email protected]> | +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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
