Abstract
dc:description.abstractThis work consists of two separate parts. The first part deals with the problem of multiple message broadcasting, and the topic of the second part is line broadcasting. Broadcasting is a process in which one vertex in a graph knows one or more messages. The goal is to inform all remaining vertices as fast as possible. In this work we consider a special kind of graphs, grids.;In 1980 A. M. Farley showed that the minimum time required to broadcast a set of M messages in any connected graph with diameter d is d + 2(M - 1). This work presents an approach to broadcasting multiple messages from the corner vertex of a 2-dimensional grid. This approach gives us a broadcasting scheme that differs only by 2 (and in the case of an even x even grid by only 1) from the above lower bound.;Line broadcasting describes a different variant of the broadcasting process. A. M. Farley showed that line broadcasting can always be completed in [log n] time units in any connected graph on n vertices. He defined three different cost measures for line broadcasting. This work presents strategies for minimizing those costs for various grid sizes.
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
-
- Wojciechowska, Iwona
Subjects
dc:subject × 1Identifiers
dc:identifier.*- Identifier
- https://researchrepository.wvu.edu/etd/3172