Destruction of very simple trees

Details Destruction of very simple trees Destruction of very simple trees

2004-12-08

arxiv.org/abs/math/0412155v2

Algorithmica, 46:3-4 (2006), pp. 345-366

Mathematics

Probability

20 pages; Version 2 corrects some minor error and fixes a few typos

Scientific paper

10.1007/s00453-006-0100-1

We consider the total cost of cutting down a random rooted tree chosen from a family of so-called very simple trees (which include ordered trees, $d$-ary trees, and Cayley trees); these form a subfamily of simply generated trees. At each stage of the process an edge is chose at random from the tree and cut, separating the tree into two components. In the one-sided variant of the process the component not containing the root is discarded, whereas in the two-sided variant both components are kept. The process ends when no edges remain for cutting. The cost of cutting an edge from a tree of size $n$ is assumed to be $n^\alpha$. Using singularity analysis and the method of moments, we derive the limiting distribution of the total cost accrued in both variants of this process. A salient feature of the limiting distributions obtained (after normalizing in a family-specific manner) is that they only depend on $\alpha$.

Affiliated with

Also associated with

No associations

Rating

Destruction of very simple trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Destruction of very simple trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Destruction of very simple trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-169977