A Caltech Library Service

Destruction of very simple trees

Fill, James Allen and Kapur, Nevin and Panholzer, Alois (2006) Destruction of very simple trees. Algorithmica, 46 (3-4). pp. 345-366. ISSN 0178-4617. doi:10.1007/s00453-006-0100-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 chosen 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^α. 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 α.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© 2006 Springer. Received December 7, 2004; revised August 4, 2005. Online publication December 13, 2006. Communicated by P. Jacquet, D. Panario, and W. Szpankowski. The research of James Allen Fill was supported by NSF Grants DMS-0104167 and DMS-0406104, and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics. Nevin Kapur’s research was supported by NSF Grant 0049092 and the Center for Mathematics of Information at the California Institute of Technology. The research of Alois Panholzer was supported by the Austrian Science Foundation FWF, Grant S9608-N13.
Funding AgencyGrant Number
Johns Hopkins UniversityUNSPECIFIED
Caltech Center for Mathematics of InformationUNSPECIFIED
FWF Der WissenschaftsfondsS9608-N13
Subject Keywords:cutting; Hadamard products; limit laws; method of moments; random spanning tree model; simply generated trees; singularity analysis; union-find
Issue or Number:3-4
Record Number:CaltechAUTHORS:20110411-072346095
Persistent URL:
Official Citation:Fill, J., Kapur, N. & Panholzer, A. Algorithmica (2006) 46: 345.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23263
Deposited By: Ruth Sustaita
Deposited On:12 Apr 2011 17:26
Last Modified:09 Nov 2021 16:12

Repository Staff Only: item control page