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.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

Identification and characterization of the transcriptional targets of the WNT/β-catenin signaling pathway in granulosa cells

Les Wnts représentent une famille de glycoprotéines de signalisation qui sont connues pour les nombreux rôles qu'ils jouent durant le développement embryonnaire et dans la cancerogénèse. Plusieurs Wnts, leurs récepteurs (Fzd) et d'autres composants des voies de signalisation des Wnt sont exprimés dans l’ovaire postnatal, et il a été démontré que l’expression de certains de ces gènes est régulée pendant le développement et l'ovulation/luteinization folliculaires. Toutefois, leurs rôles physiologiques dans l’ovaire demeurent mal définis. Pour étudier le rôle de WNT4 dans le développement folliculaire, nous avons entrepris d’identifier ses cibles transcriptionnels dans les cellules de la granulosa. Pour ce faire, nous avons employé la souris Catnbflox(ex3)/flox(ex3), chez laquelle une activation constitutive de la voie de Wnt/β-catenin a lieu suite à l’action de la recombinare Cre. Des cellules de la granulosa de ces souris ont été mises en culture et infectées avec un adenovirus pour causer la surexpression de WNT4 ou l’expression de Cre. L’ARN a alors été extrait de ces cellules et analysé par micro-puce. Les résultats ont démontré qu’une forte proportion des gènes induits par WNT4 étaient des gènes impliqués dans la réponse cellulaire au stress. Presque tous gènes induits par WNT4 ont également été induits par Cre, indiquant que WNT4 signale via la voie Wnt/β-catenin dans ces cellules. Nos résultats suggèrent donc que WNT4 favorise la survie des follicules par l’induction de gènes de réponse au stress dans les cellules de la granulosa, augmentant ainsi la résistance cellulaire à l'apoptose.