A Simple Optimal Parallel Algorithm for a Core of a Tree |
| |
| Authors: | Peng S T Lo W T |
| |
| Affiliation: | 1. Department of Civil and Environmental Engineering, The Hong Kong University of Science and Technology, Hong Kong, China;2. School of Civil Engineering, Southeast University, Nanjing, China;3. College of Civil Engineering and Architecture, Hainan University, Haikou, China |
| |
| Abstract: | A core of a tree T = (V, E) is a path in T which minimizes ∑vVd(v, P), where d(v, P), the distance from a vertex v to path P, is defined as minuPd(v, u). We present an optimal parallel algorithm to find a core of T in O(log n) time using O(n/log n) processors on an EREW PRAM machine, where n is the number of vertices of tree T. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
