Show simple item record

dc.contributor.authorLi, Yifengen_US
dc.date.accessioned2010-03-09T20:23:03Z
dc.date.available2010-03-09T20:23:03Z
dc.date.issued2010-03-09T20:23:03Z
dc.identifier.urihttp://hdl.handle.net/10464/2950
dc.description.abstractThe (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.en_US
dc.language.isoengen_US
dc.publisherBrock Universityen_US
dc.subjectTopological graph theory.en_US
dc.subjectComputer algorithms.en_US
dc.titleProperties and algorithms of the (n, k)-arrangement graphsen_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