Multiple isolation of nodes in recursive trees

MaRDI QIDQ2878855zbMATH OpenFDO

Authors Markus Kuba, Alois Panholzer

Publication date 5 September 2014

Published in Online Journal of Analytic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2880, http://www.math.rochester.edu/ojac/vol9/98.pdf

zbMATH Keywords

cutting down processlabelled treesnode isolationrecursive trees

Mathematics Subject Classification ID

Trees (05C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

Abstract: We introduce the problem of isolating several nodes in random recursive trees by successively removing random edges, and study the number of random cuts that are necessary for the isolation. In particular, we analyze the number of random cuts required to isolate $ell$ selected nodes in a size-n random recursive tree for three different selection rules, namely (i) isolating all of the nodes labelled 1,2,...,$ell$ (thus nodes located close to the root of the tree), (ii) isolating all of the nodes labelled n+1-$ell$,n+2-$ell$,...,n (thus nodes located at the fringe of the tree), and (iii) isolating $ell$ nodes in the tree, which are selected at random before starting the edge-removal procedure. Using a generating functions approach we determine for these selection rules the limiting distribution behavior of the number of cuts to isolate all selected nodes, for $ell$ fixed and n tending to infinity.

Recommendations

• Isolating nodes in recursive trees
• Isolating the most recent entry in a random recursive tree by random cuts
• Isolating a leaf in rooted trees via random cuttings
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Cited in

(12)

• Isolating the most recent entry in a random recursive tree by random cuts
• The cut-tree of large recursive trees
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• scientific article; zbMATH DE number 2127740 (Why is no real title available?)
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• Weak limits for the largest subpopulations in Yule processes with high mutation probabilities
• Cutting edges at random in large recursive trees
• A modification of the random cutting model
• A growth-fragmentation-isolation process on random recursive trees and contact tracing
• Fires on large recursive trees
• Isolating a leaf in rooted trees via random cuttings
• Isolating nodes in recursive trees

This page was built for publication: Multiple isolation of nodes in recursive trees

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