Efficient parallel algorithms forr-dominating set andp-center problems on trees |
| |
| Authors: | Xin He 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
