Breadcrumb

 
 

Broadcast networks on 2p-1 nodes and minimum broadcast network on 127 nodes

Title:

Broadcast networks on 2p-1 nodes and minimum broadcast network on 127 nodes

Xu, Xiangyang (2004) Broadcast networks on 2p-1 nodes and minimum broadcast network on 127 nodes. Masters thesis, Concordia University.

[img]
Preview
PDF - Accepted Version
8Mb

Abstract

Broadcasting is a basic problem of communication in usual networks. To design an optimal broadcast network on n nodes is very difficult. Numerous previous papers have investigated ways to construct networks with sparse communication lines in which broadcasting can be completed in the theoretically minimum amount of time from any originator. Minimum broadcast networks are the sparsest possible networks of this type, which have the minimum number of communication lines denoted by B ( n ). Many previous papers also have investigated the construction of minimum broadcast networks for small values of n . Among those, a minimum broadcast network on 63 nodes is the largest. In this thesis, a new technique of constructing broadcast networks on 2 p - 1 nodes is introduced. Furthermore, this technique is improved to construct broadcast networks on any odd number of nodes. Improved upper bounds on B ( n ) for broadcast networks on 2 p - 1 nodes are presented. Also, general bounds on B ( n ) for broadcast networks on any odd number of nodes are given. Finally, all known minimum broadcast networks on 2 p - 1 nodes are studied and common properties of them are observed. Then, careful studies of the observed properties and massive experimental work lead to the construction of a minimum broadcast network on 127 nodes. This network is proven to have 389 communication lines.

Divisions:Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Xu, Xiangyang
Pagination:ix, 113 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:2004
Thesis Supervisor(s):Harutyunyan, H. A
ID Code:7914
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:10
Last Modified:18 Aug 2011 14:10
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Document Downloads

More statistics for this item...

Concordia University - Footer