An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

被引：1
作者：
Sunder, S [1 ]
He, X [1 ]
机构：
[1] SUNY BUFFALO, DEPT COMP SCI, BUFFALO, NY 14260 USA
来源：
ALGORITHMICA | 1996年 / 16卷 / 03期
关键词：
scheduling; series parallel graphs; NC algorithms; parallel algorithm;
D O I：
10.1007/BF01955675
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O (log(2) n) time with O (n(3)) processors on a CREW PRAM, where n is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.
引用
收藏
页码：243 / 262
页数：20
相关论文
共 18 条
  • [1] A SIMPLE PARALLEL TREE CONTRACTION ALGORITHM
    ABRAHAMSON, K
    DADOUN, N
    KIRKPATRICK, DG
    PRZYTYCKA, T
    [J]. JOURNAL OF ALGORITHMS, 1989, 10 (02) : 287 - 302
  • [2] OPTIMAL LINEAR ORDERING
    ADOLPHSON, D
    HU, TC
    [J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1973, 25 (03) : 403 - 423
  • [3] CHROBAK M, 1989, LECT NOTES COMPUT SC, V382, P147
  • [4] Conway RW., 1967, THEORY SCHEDULING
  • [5] A PARALLEL MATCHING ALGORITHM FOR CONVEX BIPARTITE GRAPHS AND APPLICATIONS TO SCHEDULING
    DEKEL, E
    SAHNI, S
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1984, 1 (02) : 185 - 205
  • [6] DOLEV D, 1985, VLSI ALGORITHMS ARCH
  • [7] Graham R. L., 1979, Discrete Optimisation, P287
  • [8] PARALLEL RECOGNITION AND DECOMPOSITION OF 2 TERMINAL SERIES-PARALLEL GRAPHS
    HE, X
    YESHA, Y
    [J]. INFORMATION AND COMPUTATION, 1987, 75 (01) : 15 - 38
  • [9] 2 PROCESSOR SCHEDULING IS IN NC
    HELMBOLD, D
    MAYR, E
    [J]. SIAM JOURNAL ON COMPUTING, 1987, 16 (04) : 747 - 759
  • [10] HELMBOLD D, 1987, ADV COMPUTING RES
12