The interconnection structure of a network can have tremendous impact on the efficiency of communication and computation on the network. Highly connected networks allow short communication paths and are more resilient to failures. However, sparser networks may be more feasible to build while still providing reasonably efficient and reliable communications. An example of work in this area is the design of graph spanners - subgraphs of specific structures (such as the pyramid or the hypercube) with fewer edges in which the distance between two vertices is not significantly larger than the corresponding distance in the original structure.

Information dissemination problems concern transmitting messages from a set of senders to a set of receivers within a network. Specific information dissemination processes are defined by placing constraints on the sets of messages, senders, and receivers, on the network's topology, on the rules that govern message transmissions, and on the amount of information about the network known to individual network members.

One goal of research in this area is to design network structures which are inexpensive to construct yet allow efficient communication. An example of this work is the ongoing search for minimum broadcast graphs - the graphs with the fewest edges (for a fixed number of vertices) in which each vertex can broadcast in minimum time.

Editorial Activities: Editorial Board of Parallel Processing Letters.