Login | Register

New communication properties of Knödel graphs


New communication properties of Knödel graphs

Morosan, Calin Dan (2003) New communication properties of Knödel graphs. Masters thesis, Concordia University.

[thumbnail of MQ91088.pdf]
Text (application/pdf)
MQ91088.pdf - Accepted Version


Knödel graphs W d,n of even order n and degree d , 1 X d X [Special characters omitted.] , have been introduced by W. Knödel as a result of their good properties in terms of broadcasting and gossiping information in interconnected networks. In particular, Knödel graphs of order 2 d and degree d have been widely studied because of their remarkable number of vertices to diameter ratio characteristic, which competes with hypercubes and circulant graphs of the same order. In this thesis, a general definition of the Knödel graphs is given, based on a theorem of isomorphism, and a new family of complete rotations is found. Based on the Cayley graph definition of the Knödel graph, a new hierarchical structure is defined and its rotational properties are studied. Although Knödel graphs have high symmetry properties, the diameter of the Knödel graphs is known only for W d,2 d , and the shortest path problem in logarithmic time, is an open problem. In this thesis, a logarithmic algorithm for the shortest path in W d,2 d is proposed, for a subset of the set of vertices, and a heuristic is given for the remaining vertices. The method described here opens the way of finding the shortest path in general and for solving the general problem of finding the diameter in every Knödel graph.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Morosan, Calin Dan
Pagination:vii, 55 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Thesis Supervisor(s):Harutyunyan, Hovhannes
Identification Number:QA 90 M67 2003
ID Code:2429
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:28
Last Modified:05 Aug 2021 21:05
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

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top