Postdoctorial Visitor: H.-S. Lim
Sponsor: DARPA
In this project we study the broadcasting of messages in interconnection networks under edge reductions. Edge reductions model the decrease or elimination of broadcasting costs between adjacent nodes of the network. For example, when a communication link is replaced by a faster link, the communication time reduces and may become negligible compared to other costs. We study where to place such edge reductions so that broadcasting costs are minimized and we develop characterizations of where optimal solutions place edge reductions. We consider both blocking and non-blocking communication models and develop algorithms for various interconnection structures, including trees, outerplanar graphs, and meshes.