A k-tree core of a tree network is a subtree with exactly k leaves that minimizes the total distance from vertices to the subtree. A k-tree center of a tree network is a subtree with exactly k leaves that minimizes the distance from the farthest vertex to the subtree. In this paper, two efficient parallel algorithms are proposed for finding a k-tree core and a k-tree center of a tree network, respectively. Both the proposed algorithms perform on the EREW PRAM in O(log n log n) time using O(n) work (time-processor product). Besides being efficient on the EREW PRAM, in the sequential case, our algorithm for finding a k-tree core of a tree network improves the two algorithms previously proposed.
展开▼
机译：树网络的k树核心是具有恰好k个叶子的子树，该树使顶点到子树的总距离最小。树网络的k树中心是具有恰好k个叶子的子树，该树使从最远顶点到子树的距离最小化。本文提出了两种有效的并行算法，分别用于找到树网络的k树核心和k树中心。两种建议的算法都使用O（n）工作（时间处理器乘积）在O（log n log n）的时间内在EREW PRAM上执行。除了在EREW PRAM上高效之外，在顺序情况下，我们用于查找树网络的k树核心的算法还改进了先前提出的两种算法。
展开▼
