𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Cost of the Missing Bit: Communication Complexity with Help

✍ Scribed by László Babai; Thomas P. Hayes; Peter G. Kimmel

Book ID
106167895
Publisher
Springer-Verlag
Year
2001
Tongue
English
Weight
401 KB
Volume
21
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Complexity of Scheduling Trees with
The Complexity of Scheduling Trees with Communication Delays
✍ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-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

The Cost of Complex Communication on Sim
The Cost of Complex Communication on Simple Networks
✍ David S. Greenberg; James K. Park; Eric J. Schwabe 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 258 KB

We do not mean to denigrate the efforts to produce a general-purpose parallel machine. Machines that can realize any communication pattern are of course desirable, and necessary for those cases when the communication needs of a program cannot be predicted in advance. A wide variety of such general-p