Broadcasting in grid graphs |
Posted on:2000-03-17 | Degree:Ph.D | Type:Dissertation |
University:West Virginia University | Candidate:Wojciechowska, Iwona | Full Text:PDF |
GTID:1468390014461959 | Subject:Computer Science |
Abstract/Summary: | |
This 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. |
Keywords/Search Tags: | Broadcasting, Grid, Work, Graph |
|
Related items |