loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00)
NP-Completeness of the Bulk Synchronous Task Scheduling Problem and Its Approximation Algorithm
Dallas/Richardson, Texas, USA
December 07-December 07
ISBN: 0-7695-0936-3
ASCII Text
x 
 
N. Fujimoto, K. Hagihara, "NP-Completeness of the Bulk Synchronous Task Scheduling Problem and Its Approximation Algorithm," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 127, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2000.900276,
author = {N. Fujimoto and K. Hagihara},
title = {NP-Completeness of the Bulk Synchronous Task Scheduling Problem and Its Approximation Algorithm},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2000},
issn = {1087-4089},
pages = {127},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.900276},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - NP-Completeness of the Bulk Synchronous Task Scheduling Problem and Its Approximation Algorithm
SN - 1087-4089
SP
EP
A1 - N. Fujimoto,
A1 - K. Hagihara,
PY - 2000
KW - null
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
The bulk synchronous task scheduling problem (BSSP) is known as an effective task scheduling problem for distributed-memory machines, but the time complexity of BSSP is unknown. This paper presents a proof of NP- completeness of BSSP even in the case of unit time tasks and positive integer constant communication delays. This paper also gives an approximation algorithm for BSSP in several restricted cases.
Citation:
N. Fujimoto, K. Hagihara, "NP-Completeness of the Bulk Synchronous Task Scheduling Problem and Its Approximation Algorithm," ispan, pp.127, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000
Usage of this product signifies your acceptance of the Terms of Use.