Efficient parallel algorithms forr-dominating set andp-center problems on trees |
| |
| Authors: | Xin He and Yaacov Yesha |
| |
| Affiliation: | (1) Department of Computer Science, State University of New York at Buffalo, 14260 Buffalo, NY, USA;(2) Department of Computer and Information Science, Ohio State University, 43210 Columbus, OH, USA |
| |
| Abstract: | We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log2
n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366. |
| |
| Keywords: | Parallel algorithms Trees Optimization problems r-Dominating set p-Center |
| 本文献已被 SpringerLink 等数据库收录！ |
|
