Publications [#236671] of Bruce Maggs

Journal articles or Book chapters PUBLISHED

1. Leiserson, CE; Maggs, BM, COMMUNICATION-EFFICIENT PARALLEL GRAPH ALGORITHMS., Proceedings of the International Conference on Parallel Processing (December, 1986), pp. 861-868
   (last updated on 2024/04/24)

   Abstract:
   Communication bandwidth is a resource ignored by most parallel random-access machine (PRAM) models. It is shown that many graph problems can be solved in parallel, not only with polylogarithmic performance, but with efficient communication at each step of the computation. Measurements were made of the communication requirements of an algorithm in a model called the distributed random-access machine (DRAM), in which communication cost is measured in terms of the congestion of memory accesses across cuts of an underlying network. The algorithms are based on a communication-efficient variant of a tree contraction technique.