Show simple item record

dc.contributor.authorSalahi, Fatemeh
dc.date.accessioned2019-07-04T20:32:15Z
dc.date.available2019-07-04T20:32:15Z
dc.identifier.urihttp://hdl.handle.net/10464/14243
dc.description.abstractAn 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. 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.en_US
dc.language.isoengen_US
dc.publisherBrock Universityen_US
dc.subjectInterconnection networksen_US
dc.subjectSurface areaen_US
dc.subject(n, k)-arrangementen_US
dc.subject(n, k)-staren_US
dc.titleSurface Areas of Some Interconnection Networksen_US
dc.typeElectronic Thesis or Dissertationen_US
dc.degree.nameM.Sc. Computer Scienceen_US
dc.degree.levelMastersen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.degree.disciplineFaculty of Mathematics and Scienceen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record