Login | Register

Diameter and Broadcast Time of the Knödel graph

Title:

Diameter and Broadcast Time of the Knödel graph

Oad, Gul Bahar (2014) Diameter and Broadcast Time of the Knödel graph. Masters thesis, Concordia University.

[img]
Preview
Text (application/pdf)
Oad_MCompSc_F2014.pdf - Accepted Version
Available under License Spectrum Terms of Access.
2MB

Abstract

Efficient dissemination of information remains a central challenge for all types of networks. There are two ways to handle this issue. One way is to compress the amount of data being transferred and the second way is to minimize the delay of information distribution. Well-received approaches used in the second way either design efficient algorithms or implement reliable network architectures with optimal dissemination time. Among the well-known network architectures, the Knödel graph can be considered a suitable candidate for the problem of information dissemination. The Knödel graph W_(d, n) is a regular graph, of an even order n and degree d, 1 ≤ d ≤ floor(log n). The Knödel graph was introduced by W. Knödel almost four decades ago as network architecture with good properties in terms of broadcasting and gossiping in interconnected networks. Although the Knödel graph has a highly symmetric structure, its diameter is only known for W_(d, 2^d). Recently, the general upper and lower bounds on diameter and broadcast time of the Knödel graph have been presented.
In this thesis, our motivation is to find the diameter, the number of vertices at a particular distance and the broadcast time of the Knödel graph. Theoretically, we succeed to prove the diameter and the broadcast time of the Knödel graph W_(3, n). We also claim that the Knödel graph W_(3, n) for n = 4 mod 4 and n > 16, is a diametral broadcast graph. We present that W_(3, 22) is a broadcast graph. Experimentally, however, we obtain the following results; (a) the diameter of some specific Knödel graphs, and (b) the propositions on the number of vertices at a particular distance. We also construct a new graph, denoted as HW_(d,2^d), by connecting Knödel graph W_(d-1,2^(d-1)) to hypercube H_(d-1) and experimentally show that HW_(d,2^d) has even a smaller diameter than Knödel graph W_(d,2^d).

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Oad, Gul Bahar
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Date:16 August 2014
Thesis Supervisor(s):Harutyunyan, H. A.
ID Code:978833
Deposited By: GUL BAHAR OAD
Deposited On:10 Nov 2014 15:44
Last Modified:18 Jan 2018 17:47
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

Downloads per month over past year

Back to top Back to top