dc.contributor.author Salahi, Fatemeh dc.date.accessioned 2019-07-04T20:32:15Z dc.date.available 2019-07-04T20:32:15Z dc.identifier.uri http://hdl.handle.net/10464/14243 dc.description.abstract An interesting property of an interconnected network (G) is the number of nodes at distance i from an arbitrary processor (u), namely the node centered surface area. This is an important property of a network due to its applications in various fields of study. en_US In this research, we investigate on the surface area of two important interconnection networks, (n, k)-arrangement graphs and (n, k)-star graphs. Abundant works have been done to achieve a formula for the surface area of these two classes of graphs, but in general, it is not trivial to find an algorithm to compute the surface area of such graphs in polynomial time or to find an explicit formula with polynomially many terms in regards to the graph's parameters. Among these studies, the most efficient formula in terms of computational complexity is the one that Portier and Vaughan proposed which allows us to compute the surface area of a special case of (n, k)-arrangement and (n, k)-star graphs when k = n-1, in linear time which is a tremendous improvement over the naive solution with complexity order of O(n * n!). The recurrence we propose here has the linear computational complexity as well, but for a much wider family of graphs, namely A(n, k) for any arbitrary n and k in their defined range. Additionally, for (n, k)-star graphs we prove properties that can be used to achieve a simple recurrence for its surface area. dc.language.iso eng en_US dc.publisher Brock University en_US dc.subject Interconnection networks en_US dc.subject Surface area en_US dc.subject (n, k)-arrangement en_US dc.subject (n, k)-star en_US dc.title Surface Areas of Some Interconnection Networks en_US dc.type Electronic Thesis or Dissertation en_US dc.degree.name M.Sc. Computer Science en_US dc.degree.level Masters en_US dc.contributor.department Department of Computer Science en_US dc.degree.discipline Faculty of Mathematics and Science en_US refterms.dateFOA 2021-08-15T01:47:37Z
﻿

### Files in this item

Name:
Brock_Salahi_Fatemeh_2019
Size:
4.784Mb
Format:
PDF