CIS Logo

University of Oregon
Computer & Information Science

Communication Network Design

Principal members are:

Art Farley
Andrzej Proskurowski

We investigate the design of communication networks and algorithms for the dissemination of messages to multiple receivers in networks. Broadcasting (i.e., one-to-all), gossiping (i.e., all-to-all), and multicasting (i.e., some-to-some) represent three dissemination tasks we have addressed. The research has focussed on the design of networks with few lines that allow optimal time completion or on algorithms that allow near-optimal completion in arbitrary networks. We have recently turned our attention to multicasting, looking for efficent, virtual topologies that can support that task with minimal overhead. On another front, we have addressed problems of minimal networks that provide redundant paths between senders and receivers, thus providing some immunity to failures of sites or lines.


Farley, A.M. and Proskurowski, A., "Self-repairing networks", Parallel Processing Letters 3(4), p 381-191, (1993).

Farley, A.M. and Proskurowski, A., "Bounded-call broadcasting", Discrete Applied Mathematics, (1994).

Farley, A.M., Pelc, A., and Proskurowski, A., "Minimum-time multidrop broadcast", Discrete Applied Mathematics, (1995).

Fujita, S. and Farley, A. M., "Line broadcasting in paths", Discrete Applied Mathematics, (1996).

Farley, A.M. and Proskurowski, A., "Minimum self-repairing graphs", Graphs and Combinatorics, (1997).

Farley, A.M., "Optimally Routable Networks", Parallel Processing Letters, (1998).

Farley, A.M., Fragopoulou, P., Krumme, D.,and Proskurowski, A., "Multisource spanning tree problems", Journal of Interconnection Networks, 1, p61-71, (2000).

Fujita, S. and Farley, A.M., "Sparse hypercube: A minimal k-line broadcast graph", Discrete Applied Mathematics, p431-446, (2003).

Farley, A.M., Proskurowski, A., Windisch, K., and Zappala, D., "Spanners and message distribution in networks", Discrete Applied Mathematics, p159-171, (2004).

Farley, A.M., "Minimal path broadcast networks", Networks, p61-70, (2004).