Back to search

West Virginia University

Information dissemination by compounding

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
PhD
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Lane Department of Computer Science and Electrical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Bohe (Bob)

Subjects

dc:subject × 1

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wang, Bohe (Bob). Information dissemination by compounding. Dissertation thesis, https://doi.org/10.33915/etd.2128