A New Linear-Time Algorithm for Centroid Decomposition
A New Linear-Time Algorithm for Centroid Decomposition
复制标题
一种新的质心分解线性时间算法
DOI：
10.1007/978-3-030-32686-9_20
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Rossano Venturini
中科院分区：
文献类型：
--
作者：
D. D. Giustina;N. Prezza;Rossano Venturini
树的质心是一个节点，当被移除时，它将树分成大小最多为原始树的一半的连通分量。通过在分量上递归这个过程，可以得到树的质心分解，也称为质心树。质心树具有对数高度，它的构造是几种树处理算法中强有力的预处理步骤。计算质心树的民俗递归算法运行时间为O(n\logn)。就我们所知，唯一需要O(N)时间的结果是未发布的，并且依赖于原始树的(动态)重路径分解。在这篇短文中，我们描述了一种新的简单实用的线性时间算法，该算法基于将民俗算法应用于对原始树进行适当分解的思想。
The centroid of a tree is a node that, when removed, breaks the tree in connected components of size at most half of that of the original tree. By recursing this procedure on the components, one obtains the centroid decomposition of the tree, also known as centroid tree. The centroid tree has logarithmic height and its construction is a powerful pre-processing step in several tree-processing algorithms. The folklore recursive algorithm for computing the centroid tree runs in \(O(n\log n)\) time. To the best of our knowledge, the only result claiming O(n) time is unpublished and relies on (dynamic) heavy path decomposition of the original tree. In this short paper, we describe a new simple and practical linear-time algorithm for the problem based on the idea of applying the folklore algorithm to a suitable decomposition of the original tree.