THE COMPLEXITY OF SCHEDULING TREES WITH COMMUNICATION DELAYS

Authors
LENSTRA JK VELDHORST M VELTMAN B
Citation
Jk. Lenstra et al., THE COMPLEXITY OF SCHEDULING TREES WITH COMMUNICATION DELAYS, Journal of algorithms, 20(1), 1996, pp. 157-173
Citations number
16
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
20
Issue
1
Year of publication
1996
Pages
157 - 173
Database
ISI
SICI code
0196-6774(1996)20:1<157:TCOSTW>2.0.ZU;2-9
Abstract
We consider the problem of finding a minimum-length schedule on m mach ines for a set of n unit-length tasks with a forest of intrees as prec edence relation, and with unit interprocessor communication delays. Fi rst, we prove that this problem is NP-complete; second, we derive a li near time algorithm for the special case that m equals 2. (C) 1996 Aca demic Press, Inc.