An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs |
| |
| Authors: | S. Sunder Xin He |
| |
| Affiliation: | (1) Department of Computer and Information Sciences, University of Delaware, 19716 Newark, DE, USA;(2) Department of Computer Science, State University of New York at Buffalo, 14260 Buffalo, NY, USA |
| |
| Abstract: | We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log2n) time withO(n3) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982. |
| |
| Keywords: | Scheduling Series parallel graphs NC algorithms Parallel algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
