Breadcrumb

 
 

New communication properties of Knödel graphs

Title:

New communication properties of Knödel graphs

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

[img]
Preview
PDF - Accepted Version
1544Kb

Abstract

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 > Faculty 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:Theses (M.Comp.Sc.)
Program:Dept. of Computer Science
Date:2003
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:2429
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:28
Last Modified:14 Dec 2012 16:36
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