A new parallel algorithm for rooting a tree |
| |
| Authors: | Taenam Kim Dukhwan Oh Eunki Lim |
| |
| Affiliation: | 1. Department of Computer Engineering, Kumoh National University of Technology Sinpyeongdong, Kumisi, Kyeongbook, Korea
|
| |
| Abstract: | When an undirected tree,T, and a vertex,r, in the tree are given, the problem to transformT into a rooted tree withr as its root is considered. Using Euler tour and prefix sum, an optimal algorithm has been developed [2, 3]. We will present another parallel algorithm which is optimal also on EREW PRAM. Our approach reduces the given tree step by step by pruning and pointer jumping. That is, the tree structure is retained during algorithm processing such that another tree computations can be carried out in parallel. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
