Semester

Summer

Date of Graduation

2004

Document Type

Dissertation

Degree Type

PhD

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

Frances L. Van Scoy.

Abstract

Gossiping and broadcasting are two problems of information dissemination. In gossiping, every point in the network knows a unique item of information and needs to communicate it to all other points. Most of the recent interest in gossiping is due to its importance in the area of network communications and other areas of parallel and distributed computing.;Determining precisely the values of the minimum number of edges in a gossip graph is known to be a very hard problem. Very few values are known in the general case. G. Fertin and R. Labahn[Fer00],[FL00] used the k-way compounding method to construct gossip graphs from existing gossip graphs. They considered the cases k = 2,3,5,9,10,12. Their work shows that the compounding method is useful for obtaining upper bounds. They obtained results for even numbers of vertices in cases of 128 vertices or less.;In this dissertation, we utilize 4, 6, 7, 8, and 11 way compounding methods. This is the first time that these methods have been used. In this dissertation, we designed an algorithm and programmed it to compute and compare all possibilities to obtain the best results. We consider graphs with n vertices, all even values of n less than 256. In addition to obtaining results for new values of n, we are able to improve three of G. Fertin and R. Labahn's results. For n = 76, their number of edges in a gossip graph is 170; our result is 166. For n = 82, their result is 197; our result is 193. For n = 98, their result is 294; our result is 245.*.;*This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat.

Download

Share

COinS