An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs

S. Sunder; Xin He

doi:10.1007/bf01955675

An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs

S. Sunder
, Xin He

Department of Computer Science and Engineering

University of Delaware

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O(log² n) time with O(n³) 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.

Original language	English
Pages (from-to)	243-262
Number of pages	20
Journal	Algorithmica
Volume	16
Issue number	3
DOIs	https://doi.org/10.1007/bf01955675
State	Published - Sep 1996

Keywords

NC algorithms
Parallel algorithm
Scheduling
Series parallel graphs

Access to Document

10.1007/bf01955675

Cite this

@article{cd6d113e27f645229c96e5c0c1455cac,

title = "An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs",

abstract = "We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O(log2 n) time with O(n3) 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.",

keywords = "NC algorithms, Parallel algorithm, Scheduling, Series parallel graphs",

author = "S. Sunder and Xin He",

year = "1996",

month = sep,

doi = "10.1007/bf01955675",

language = "English",

volume = "16",

pages = "243--262",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs

AU - Sunder, S.

AU - He, Xin

PY - 1996/9

Y1 - 1996/9

N2 - We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O(log2 n) time with O(n3) 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.

AB - We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O(log2 n) time with O(n3) 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.

KW - NC algorithms

KW - Parallel algorithm

KW - Scheduling

KW - Series parallel graphs

UR - https://www.scopus.com/pages/publications/0003171625

U2 - 10.1007/bf01955675

DO - 10.1007/bf01955675

M3 - Article

AN - SCOPUS:0003171625

SN - 0178-4617

VL - 16

SP - 243

EP - 262

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -

An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this