My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
November 16th, 2008, 01:46 AM   #1
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.

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.
Shaitan00 is offline  

  My Math Forum > Science Forums > Computer Science

depthdetermination, problem, pseudodistances

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Calculation of rank in Simplicial depth aww78 Advanced Statistics 0 April 22nd, 2012 02:02 AM
Probability of gender determination stuarty77 Probability and Statistics 3 June 4th, 2011 04:33 PM
Penetration depth of two convex polyhedrons. 1101 Algebra 0 March 8th, 2011 12:21 PM
Pseudo-finite fields Mathworm Abstract Algebra 1 March 5th, 2009 02:20 PM
Pseudo-Diophantine Nuisance reddmann Number Theory 2 August 30th, 2007 08:03 AM

Copyright © 2019 My Math Forum. All rights reserved.