arXiv:2410.06481math.PRcs.DS2024-10被引 3
通过反复剔除叶子节点，可高效定位树结构中的根节点。
Leaf Stripping on Uniform Attachment Trees
- 用迭代剔除叶子节点的方法寻找树的根。
- 在概率1-ε下，剩余节点数仅与ε有关，与树大小无关。
- 适合处理大规模随机树结构的根定位问题。
本文分析了一种简单根定位算法在均匀附加树中的表现。该算法通过递归剔除树中所有叶子节点，经过精心选择的若干轮操作后，我们证明：以概率1−ε，剩余顶点集合包含根节点，且其大小仅依赖于ε，而与树的规模无关。
原文摘要 · Abstract (English)
In this note we analyze the performance of a simple root-finding algorithm in uniform attachment trees. The leaf-stripping algorithm recursively removes all leaves of the tree for a carefully chosen number of rounds. We show that, with probability $1 - ε$, the set of remaining vertices contains the root and has a size only depending on $ε$ but not on the size of the tree.
图算法根定位随机树
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。