The complexity of scheduling trees with communication delays

J.K. Lenstra, M. Veldhorst, B. Veltman

Research output: Contribution to journalArticleAcademicpeer-review

33 Citations (Scopus)


We consider the problem of finding a minimum-length schedule onmmachines for a set ofnunit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm for the special case that m equals 2.
Original languageEnglish
Pages (from-to)157-173
Number of pages17
JournalJournal of Algorithms
Issue number1
Publication statusPublished - 1996


Dive into the research topics of 'The complexity of scheduling trees with communication delays'. Together they form a unique fingerprint.

Cite this