Properties and algorithms of the (n, k)-arrangement graphs

The (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.

Johns-Manville (Canada) records, 1949-1977 (non-inclusive).

The Johns-Manville Company was founded in 1901with the merging of the H.W. Johns Manufacturing Company and the Manville Covering Company. Both companies made building materials using asbestos. The new company was based in New York, New York, and made products such as insulation and roofing materials, automotive sheet packing for cylinders, asbestos/cement, acoustical and magnesia products. Significant restructuring has occurred over the years as the company shifted from production of asbestos products to other types of building materials, such as fibre glass and forest products. Since 2001, the Johns-Manville Company has been owned by Berkshire Hathaway. The company began operations in Canada in 1918 in Asbestos, Quebec, where the Jeffrey Asbestos Mine was located. A Canadian plant opened in Port Union, Scarborough Township, in 1956, and another in North Bay, Ontario, in 1957. Both of these plants have since closed. The company currently has two plants in Canada, in Innisfail, Alberta, and Cornwall, Ontario.

Dynamics in large scale networks

In this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the Barabási-Albert random graph. We establish some bounds on the number of motifs in this graph.