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 等数据库收录! |
|