Network failures can originate from or be located in any one of several network layers as described by the OSI model. This investigation focuses on the role of physical topological design parameters in determining network reliability and performance as can be expected from the point of view of a typical client-server based connection in an Ethernet local area network. This type of host-to-host IP connection is found in many commercial, military and industrial network based systems. Using Markov modelling techniques reliability and performability models are developed for common network topologies based on the redundancy mechanism provided by IEEE spanning tree protocols. The models are tested and validated using the OPNET network simulation environment. The reliability and performability metrics calculated from the derived models for different topologies are compared leading to the following conclusions. The reliability of the entry-nodes into a redundant network is a determining factor in connection availability. Redundancy mechanisms must be extended from the entry-node to the connecting hosts to gain a significant benefit from redundant network topologies as network availability remains limited to three-nines. The hierarchical mesh network offers the highest availability (sevennines) and performability. Both these metrics can be accurately predicted irrespective of the position of the entry-node in the mesh. Ring networks offer high availability (five to sevennines) and performability if the ring remains small to medium sized, however for larger rings (N≥32) the availability is highly dependant on the relative position of the entry-node in the ring. Performability also degrades significantly as the ring size increases. Although star networks offer predictable and high performability the availability is low (four-nines) because of the lack of redundancy. The star should therefore not be used in IP networked systems requiring more than four-nines availability. In all the topologies investigated the reliability and performability can be increased significantly by introducing redundant links instead of single links interconnecting the various nodes, with the star topology availability increasing from four-nines to seven-nines and performance doubling. / MIng (Computer and Electronic Engineering), North-West University, Potchefstroom Campus, 2014

Network failures can originate from or be located in any one of several network layers as described by the OSI model. This investigation focuses on the role of physical topological design parameters in determining network reliability and performance as can be expected from the point of view of a typical client-server based connection in an Ethernet local area network. This type of host-to-host IP connection is found in many commercial, military and industrial network based systems. Using Markov modelling techniques reliability and performability models are developed for common network topologies based on the redundancy mechanism provided by IEEE spanning tree protocols. The models are tested and validated using the OPNET network simulation environment. The reliability and performability metrics calculated from the derived models for different topologies are compared leading to the following conclusions. The reliability of the entry-nodes into a redundant network is a determining factor in connection availability. Redundancy mechanisms must be extended from the entry-node to the connecting hosts to gain a significant benefit from redundant network topologies as network availability remains limited to three-nines. The hierarchical mesh network offers the highest availability (sevennines) and performability. Both these metrics can be accurately predicted irrespective of the position of the entry-node in the mesh. Ring networks offer high availability (five to sevennines) and performability if the ring remains small to medium sized, however for larger rings (N≥32) the availability is highly dependant on the relative position of the entry-node in the ring. Performability also degrades significantly as the ring size increases. Although star networks offer predictable and high performability the availability is low (four-nines) because of the lack of redundancy. The star should therefore not be used in IP networked systems requiring more than four-nines availability. In all the topologies investigated the reliability and performability can be increased significantly by introducing redundant links instead of single links interconnecting the various nodes, with the star topology availability increasing from four-nines to seven-nines and performance doubling. / MIng (Computer and Electronic Engineering), North-West University, Potchefstroom Campus, 2014

Thesis (MSc)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: The main objective of our study is enumerating spanning trees (G) and perfect matchings PM(G) on graphs G and lattices L. We demonstrate two methods of enumerating spanning trees of any connected graph, namely the matrix-tree theorem and as a special value of the Tutte polynomial T(G; x; y). We present a general method for counting spanning trees on lattices in d 2 dimensions. In particular we apply this method on the following regular lattices with d = 2: rectangular, triangular, honeycomb, kagomé, diced, 9 3 lattice and its dual lattice to derive a explicit formulas for the number of spanning trees of these lattices of finite sizes. Regarding the problem of enumerating of perfect matchings, we prove Cayley’s theorem which relates the Pfaffian of a skew symmetric matrix to its determinant. Using this and defining the Pfaffian orientation on a planar graph, we derive explicit formula for the number of perfect matchings on the following planar lattices; rectangular, honeycomb and triangular. For each of these lattices, we also determine the bulk limit or thermodynamic limit, which is a natural measure of the rate of growth of the number of spanning trees (L) and the number of perfect matchings PM(L). An algorithm is implemented in the computer algebra system SAGE to count the number of spanning trees as well as the number of perfect matchings of the lattices studied. / AFRIKAANSE OPSOMMING: Die hoofdoel van ons studie is die aftelling van spanbome (G) en volkome afparings PM(G) in grafieke G en roosters L. Ons beskou twee metodes om spanbome in ’n samehangende grafiek af te tel, naamlik deur middel van die matriks-boom-stelling, en as ’n spesiale waarde van die Tutte polinoom T(G; x; y). Ons behandel ’n algemene metode om spanbome in roosters in d 2 dimensies af te tel. In die besonder pas ons hierdie metode toe op die volgende reguliere roosters met d = 2: reghoekig, driehoekig, heuningkoek, kagomé, blokkies, 9 3 rooster en sy duale rooster. Ons bepaal eksplisiete formules vir die aantal spanbome in hierdie roosters van eindige grootte. Wat die aftelling van volkome afparings aanbetref, gee ons ’n bewys van Cayley se stelling wat die Pfaffiaan van ’n skeefsimmetriese matriks met sy determinant verbind. Met behulp van hierdie stelling en Pfaffiaanse oriënterings van planare grafieke bepaal ons eksplisiete formules vir die aantal volkome afparings in die volgende planare roosters: reghoekig, driehoekig, heuningkoek. Vir elk van hierdie roosters word ook die “grootmaat limiet” (of termodinamiese limiet) bepaal, wat ’n natuurlike maat vir die groeitempo van die aantaal spanbome (L) en die aantal volkome afparings PM(L) voorstel. ’n Algoritme is in die rekenaaralgebra-stelsel SAGE geimplementeer om die aantal spanboome asook die aantal volkome afparings in die toepaslike roosters af te tel.

Spanning tree congestion was defined by Ostrovskii (2004) as a measure of how well a network can perform if only minimal connection can be maintained. We compute the parameter for several families of graphs. In particular, by partitioning a hypercube into pieces with almost optimal edge-boundaries, we give tight estimates of the parameter thereby disproving a conjecture of Hruska (2008). For a typical random graph, the parameter exhibits a zigzag behaviour reflecting the feature that it is not monotone in the number of edges. This motivates the study of the most congested graphs where we show that any graph is close to a graph with small congestion. Next, we enumerate independent sets. Using the independent set polynomial, we compute the extrema of averages in trees and graphs. Furthermore, we consider inverse problems among trees and resolve a conjecture of Wagner (2009). A result in a more general setting is also proved which answers a question of Alon, Haber and Krivelevich (2011). After briefly considering polynomial invariants of general graphs, we specialize into trees. Three levels of tree distinguishing power are exhibited. We show that polynomials which do not distinguish rooted trees define typically exponentially large equivalence classes. On the other hand, we prove that the rooted Ising polynomial distinguishes rooted trees and that the Negami polynomial determines the subtree polynomial, strengthening results of Bollobás and Riordan (2000) and Martin, Morin and Wagner (2008). The top level consists of the chromatic symmetric function and it is proved to be a complete invariant for caterpillars.

This dissertation consists of two essays. First essay investigates the implications of researcher data requirement on the risk-adjusted returns of firms. Using the monthly CRSP data from 1925 to 2013, we present evidence that firms which survive longer have higher average returns and lower standard deviation of annualized returns than the firms which do not. I further demonstrate that there is a positive relation between firms’ survival and average performance. In order to account for the positive correlation between survival and average performance, I model the relation of survival and pricing errors using a Farlie-Gumbel-Morgenstern joint distribution function and fit resulting the moment conditions to the data. Our results show that even a low correlation between firm survival time and pricing errors can lead to a much higher correlation between the survival time and average pricing errors. Failure to adjust for this data selection biases can result in over/under estimates of abnormal returns by 5.73 % in studies that require at least five years of returns data. Second essay examines diversification benefits of commodity futures portfolios in the light of the rapid increase in investor participation in commodity futures market since 2000. Many actively managed portfolios outperform traditional buy and hold portfolios for the sample period from January, 1986 to October, 2013. The evidence documented through traditional intersection test and stochastic discount factor based spanning test indicates that financializaiton has reduced segmentation of commodity market with equity and bond market and has increased the riskiness of investing in commodity futures markets. However, diversifying property of commodity portfolios have not disappeared despite the increased correlation between commodity portfolios returns and equity index returns.

Research has shown that socially-focused partnerships that cross sectors (referred to as social partnerships within) are necessary in order to effectively address pressing societal issues such as poverty. Yet, in these complex organizational contexts, there is often variability within and between involved organizations as it relates to basic assumptions around work and the meanings given to practices at macro, meso and micro levels of analysis. Put differently, there are often a plurality of meaning systems at play in such multi-faceted organizational arrangements. Accordingly, the purpose of this dissertation was to understand to what extent multiple meaning systems exist in social partnerships focused on addressing multi-faceted societal challenges and, whether and how such differences in meaning systems are strategically negotiated over time. At a deeper theoretical level, this research was focused on illuminating the processes by which meaning systems are negotiated when organizational boundaries are blurred and when a plurality of meaning systems are at play, with a central focus on players that act as boundary spanners within these complex organizational contexts. To understand the complexities at play in social partnerships emanating from multiple meaning systems, I conducted a multi-site ethnographic study, involving in-depth interviews and participant observation, of the Greater Victoria Coalition to End Homelessness Society (Coalition) located in Victoria, British Columbia. In doing so, I utilized the principal literature streams that address multiple meaning systems at work: the culture literature in organization studies and the institutional logics perspective. As well, I incorporated other literatures based upon the emergent findings, namely organizational identity. Through this work I make a number of contributions within the area of sustainability, particularly the social partnership literature, as well as organizational theory. Empirically, I develop a process model that elucidates how players negotiate multiple meanings of organizational identity over time in a social partnership setting characterized by permeable boundaries and shared authority, at the group level of analysis. This is significant as we know little about how identity plays out in such multi-faceted organizational settings with continual blurred boundaries even as research has indicated that such arrangements are likely to surface identity issues among players (Maguire & Hardy, 2005). I also elucidate how individual players bridge across multiple meaning systems in a social partnership over time, answering the call for more research concerning the role of individuals and their interactions with organizations in the collaboration process over time (Manning & Roessler, 2014). To my knowledge, this work is one of the first of its kind to empirically explore tri-sector socially focused collaborations – involving players from the public, private and nonprofit sectors – that are more integrative and interconnected in nature (Austin & Seitanidi, 2012a) and that employs a process based perspective to understand how such collaborations unfold over time. In addition, I theoretically develop the link between institutional logics and organizational culture that emerged empirically via this study to guide future integrative work to holistically account for the multiplicity of meaning systems at work within and between such multi-faceted arrangements. / Graduate / 2020-04-01

Nous nous intéressons aux lacets markoviens définis dans le cadre de la théorie des chaînes de Markov à temps continu sur un espace d'états discret. Ce sujet a notamment été étudié par Le Jan [LJ11] et Sznitman [Szn12]. En contraste avec ces références, nous ne supposerons pas la symétrie de la chaîne et nous intéresserons plutôt au cas infini. Tous les résultats sont présentés en termes de générateur de semi-groupe. En comparaison avec [LJ11], certaines preuves ont été détaillées ou améliorées.Nous fournissons par ailleurs quelques résultats sur les amas de boucles (voir [LJL12] dans le cas symétrique). Nous traitons notamment l'exemple du cercle discret. Nous étudions aussi les arbres couvrants définit par l'algorithme de Wilson dans le cas asymétrique.Dans la dernière partie, nous considérons la proportion des lacets couvrants l'espace. En utilisant la limite du spectre, nous donnons une expression générale de la limite de cette proportion pour une suite de graphes. Comme une application, nous donnons deux exemples concrets dans lesquels une transition de phase apparaît. / We are interested in Markov laces defined in the framework of the theory of Markov chains in continuous time on a discrete state space. This particular subject has been studied by Le Jan [LJ11] and Sznitman [Szn12]. In contrast to these references, we do not assume the reversibility of the chain and we are mostly interested in the case of countable state space. All the results are presented in terms of the generator of semigroup. In comparison with [LJ11], some demonstration has been detailed or improved.We also provide some results on the loop clusters (see [LJL12] in the reversible case). In particular, we study the example of discrete circle. We also study the spanning tree algorithm defined by Wilson in the non-symmetric case.In the last part, we consider the proportion of loops covering the whole space. Using the limit of the spectrums, we give a general expression for the limit of this ratio for a sequence of graphs. As an application, we give two examples in which a phase transition occurs.

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.

This thesis consists of one stock return predictability study and two international risk exposure studies. The first study shows that the statistical significance of out-of-sample predictability of market returns given by Kelly and Pruitt (2013), using a partial least squares methodology, constructed from the valuation ratios of portfolios, is overstated for two reasons. Firstly, the analysis is conducted on gross returns rather than excess returns, and this raises the apparent predictability of the equity premium due to the inclusion of predictable movements of interest rates. Secondly, the bootstrap statistics used to assess out-of-sample significance do not account for small-sample bias in the estimated coefficients. This bias is well known to affect in-sample tests of significance and I show that it is also important for out-of-sample tests of significance. Accounting for both these effects can radically change the conclusions; for example, the recursive out-of-sample R2 values for the sample period 1965-2010 are insignificant for the prediction of one-year excess returns, and one-month returns, except in the case of the book-to-market ratios of six size- and value-sorted portfolios which are significant at the 10% level. The second study examines whether U.S. common stocks are exposed to international risks, which I define as shocks to foreign markets that are orthogonal to U.S. market returns. By sorting stocks on past exposure to this risk factor I show that it is possible to create portfolios with an ex-post spread in exposure to international risk. I examine whether the international risk is priced in the cross-section of U.S. stocks, and find that for small stocks an increase in exposure to international risk results in lower returns relative to the Fama-French three-factor model. I conduct similar analysis on a measure of the international value premium and find little evidence of this risk being priced in U.S. stocks. The third study examines whether a portfolios of U.S. stocks can mimic foreign index returns, thereby providing investors with the benefits of international diversification without the need to invest directly in assets that trade abroad. I test this proposition using index data from seven developed markets and eight emerging markets over the period 1975-2013. Portfolios of U.S. stocks are constructed out-of-sample to mimic these international indices using a step-wise procedure that selects from a variety of industry portfolios, stocks of multinational corporations, country funds and American depositary receipts. I also use a partial least squares approach to form mimicking portfolios. I show that investors are able to gain considerable exposure to emerging market indices using domestically traded stocks. However, for developed market indices it is difficult to obtain home-made exposure beyond the simple exposure of foreign indices to the U.S. market factor. Using mean-variance spanning tests I find that, with few exceptions, international indices do not improve over the investment frontier provided by the domestically constructed alternative of investing in the U.S. market index and portfolios of industries and multinational corporations.

After recognizing the beauty and the utility of Graph Theory in solving a variety of problems, the author decided that it would be a good idea to make the subject available for students earlier in their educational experience. In this thesis, the author developed four units in Graph Theory, namely Vertex Coloring, Minimum Spanning Tree, Domination, and Hamiltonian Paths and Cycles, which are appropriate for high school level.