My Math Forum Pseudo-Distances within a depth-determination problem

 Computer Science Computer Science Forum

 November 16th, 2008, 01:46 AM #1 Newbie   Joined: Sep 2008 Posts: 8 Thanks: 0 Pseudo-Distances within a depth-determination problem I was given the following problem description for a depth-determination problem, however I am completly unable to figure out how this "pseudo-distance" feature works, if anyone has any clues and can provide a uber-simple example it would be much appreciated - I just can't see how it works/applies. [Problem] In the depth-determination problem, we maintain a forest F = {Ti} of rooted trees. We use the disjoint-set forest S=Si, where each set Si (which is itself a tree) corresponds to a tree Ti in the forest F. The tree structure within a set Si, however, does not necessarily correspond to that of Ti. In fact, the implementation of Si does not record the exact parent-child relationships but nevertheless allows us to determine any node’s depth in Ti. The key idea is to maintain each node v a ”pseudo-distance” d[v], which is defined so that the sum of the pseudo-distances along the path from v to the root of its set Si equals the depth of v in Ti. That is, if the path from v to its root in v0 , v1 , . . . , vk , where v0 = v and vk is Si’s root, then the depth of v in Ti is the sum of d[vj] where j=0 to j=k.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post aww78 Advanced Statistics 0 April 22nd, 2012 02:02 AM stuarty77 Probability and Statistics 3 June 4th, 2011 04:33 PM 1101 Algebra 0 March 8th, 2011 12:21 PM Mathworm Abstract Algebra 1 March 5th, 2009 02:20 PM reddmann Number Theory 2 August 30th, 2007 08:03 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top