Destruction of very simple trees

DOI10.1007/S00453-006-0100-1zbMATH Open1106.68081arXivmath/0412155OpenAlexW3103793925MaRDI QIDQ866949FDOQ866949

Authors: James Allen Fill, Nevin Kapur, Alois Panholzer 

Publication date: 14 February 2007

Published in: Algorithmica (Search for Journal in Brave)

Abstract: 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^{a}lpha$. 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$.

Full work available at URL: https://arxiv.org/abs/math/0412155

Recommendations

• Cutting down very simple trees
• scientific article; zbMATH DE number 2127740
• scientific article; zbMATH DE number 7703259
• Cuts in increasing trees
• Splitting trees
• Forest defoliation scenarios
• Growing and destroying Catalan-Stanley trees
• When bad things happen to good trees
• Blame trees
• scientific article; zbMATH DE number 5033862

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Cited In (12)

• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• Cutting down very simple trees
• Reducing simply generated trees by iterative leaf cutting
• Title not available (Why is that?)
• Inverting the cut-tree transform
• Woodland deforestation by charcoal supply to Dar es Salaam
• Title not available (Why is that?)
• Cutting down trees with a Markov chainsaw
• The uncover process for random labeled trees
• Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
• The cut-tree of large trees with small heights
• Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent

This page was built for publication: Destruction of very simple trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866949)