In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed.<p><p>We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time.<p><p>We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results.<p><p>After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances.<p><p>Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them.<p><p>Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case.<p><p>------------------------------------------------<p><p>Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits.<p><p>Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes.<p><p>Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3.<p><p>Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème.<p><p>Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas. <p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

Cette thèse se divise en deux parties. Nous nous intéressons dans un premier temps à des fragmentations d'arbres aléatoires, et aux arbres des coupes associés. Dans le cadre discret, les modèles étudiés sont des arbres de Galton-Watson, fragmentés en enlevant successivement des arêtes choisies au hasard. Nous étudions également leurs analogues continus, l'arbre brownien et les arbres stables, que l'on fragmente en supprimant des points donnés par des processus ponctuels de Poisson. L'arbre des coupes associé à l'un de ces processus, discret ou continu, décrit la généalogie des composantes connexes créées au fur et à mesure de la dislocation. Pour une fragmentation qui se concentre autour de nœuds de grand degré, nous montrons que l'arbre des coupes continu est la limite d'échelle des arbres des coupes discrets correspondants. Dans les cas brownien et stable, nous montrons également que l'on peut reconstruire l'arbre initial à partir de son arbre des coupes et d'un étiquetage bien choisi de ses points de branchement. Nous étudions ensuite un problème portant sur les cartes aléatoires, et plus précisément sur la quadrangulation uniforme infinie du plan (UIPQ). De récents résultats montrent que dans l'UIPQ, toutes les géodésiques infinies issues de la racine sont essentiellement similaires. Nous déterminons la quadrangulation limite obtenue en ré-enracinant l'UIPQ ''à l'infini'' sur de l'une de ces géodésiques. Cette étude se fait en découpant l'UIPQ le long de cette géodésique. Nous étudions les deux parties ainsi créées via une correspondance avec des arbres discrets, puis nous obtenons la limite souhaitée par recollement. / This PhD thesis is divided into two parts. First, we study some fragmentations of random trees and the associated cut-trees. The discrete models we are interested in are Galton-Watson trees, which are cut down by recursively removing random edges. We also consider their continuous counterparts, the Brownian and stable trees, which are fragmented by deleting the atoms of Poisson point processes. For these discrete and continuous models, the associated cut-tree describes the genealogy of the connected components which appear during the cutting procedure. We show that for a ''vertex-fragmentation'', in which the nodes having a large degree are more susceptible to be deleted, the continuous cut-tree is the scaling limit of the corresponding discrete cut-trees. In the Brownian and stable cases, we also give a transformation which rebuilds the initial tree from its cut-tree and a well chosen labeling of its branchpoints. The second part relates to random maps, and more precisely the uniform infinite quadrangulation of the plane (UIPQ). Recent results show that in the UIPQ, all infinite geodesic rays originating from the root are essentially similar. We identify the limit quadrangulation obtained by rerooting the UIPQ at a point ''at infinity'' on one of these geodesics. To do this, we split the UIPQ along this geodesic ray. Using a correspondence with discrete trees, we study the two sides, and obtain the desired limit by gluing them back together.

Les récepteurs de type Toll (TLR) sont des récepteurs cellulaires jouant un rôle pivot dans le déclenchement de la réponse immunitaire après une infection ou une blessure, c'est-à-dire une inflammation. L'activation de la signalisation TLR a été associée à l’épilepsie. Dans ce projet, j'utilisai trois modèles distincts pour étudier comment le déclenchement des TLR contribue à l'épileptogenèse. Il existe une corrélation entre les malformations corticales développementales telle la dysplasie corticale focale (FCD) et convulsions fébriles dans les enfants de bas âge. Récemment, une réponse neuro-inflammatoire fut identifiée dans les lésions FCD. Nous postulâmes que l'inflammation induite par le FCD peut augmenter la sensibilité aux crises (chapitre 2). Nous modélisâmes FCD en induisant une congélation-lésion corticale chez le rat néonatal. La lésion corticale déclencha des effecteurs en aval de TLR4, spécifiquement le précurseur de la cytokine Caspase-1, dans l'hippocampe ipsilatéral à la lésion. Les rats lésés développèrent des crises fébriles expérimentales nettement plus rapidement que les rats témoins. Le blocage de l'activité de la Caspase-1 prolongea significativement la latence des crises chez les rats lésés. Nos résultats impliquent l'inflammation médiée par la Caspase-1 en tant que déclencheur des crises fébriles chez les enfants avec FCD préexistante. Des études antérieures déterminèrent que l'activation systémique de la cascade TLR4 abaisse le seuil de crise. Nous étudiâmes si la pénétration des cellules immunitaires périphériques dans le cerveau pendant la stimulation TLR4 favorise l'activité ictal en stimulant la voie TLR4 dans les leucocytes prélevés sur la rate de rat (splénocytes). Ensuite, nous co-cultivâmes des splénocytes avec des coupes organotypiques dérivées du cerveau in vitro (chapitre 3). L'ajout de splénocytes stimulés par TLR4 donna lieu à une neuro-inflammation et à une excitation neuronale accrue. L’ajout de splénocytes non-stimulés n’eut aucun effet pro-inflammatoire ou pro-excitateur dans les coupes organotypiques. De plus, l'inhibition de la Caspase-1 dans des coupes organotypiques co-cultivées avec des splénocytes stimulés diminua la neuro-inflammation et l'hyperexcitabilité neuronale. Nos résultats suggèrent que l'infiltration de leucocytes activés par TLR4 dans le cerveau augmente la prédisposition aux crises via les mécanismes médiés par la Caspase-1. Précédemment, des rapports montrèrent que l'activation de la signalisation TLR3 facilite l'évolution des crises. L'introduction d'un agoniste synthétique TLR3 chez la souris in vivo et des coupes organotypiques hippocampiques in vitro produisirent des mécanismes anti-inflammatoires dépendants de la dose et du temps (chapitre 4). La stimulation TLR3 supprimait les crises d'hippocampe in vivo et réduisait l'excitabilité synaptique dans le réseau hippocampique à la fois in vivo et in vitro. Nous avons déterminé que les effets anticonvulsivants médiés par TLR3 étaient principalement provoqués par les cascades en aval IRF3 / IFN-β. Ainsi, nos données suggèrent que l'activation de TLR3 peut protéger le cerveau contre les crises par la production d'IFN-β. Nos résultats donnent un aperçu des nouveaux mécanismes cellulaires sous-jacents à la modulation inflammatoire de l'excitabilité neurale. Notre découverte des rôles de la Caspase-1 et de l'IFN-β dans l'influence du seuil de crise améliorera notre compréhension des fondements moléculaires de la génération de crises ce qui pourraient améliorer le traitement de l'épilepsie. / Toll-like receptors (TLRs) are cellular receptors that play a pivotal role in initiating immune response following infection or injury, i.e. inflammation. Nevertheless, activation of TLR signaling has been associated with seizure manifestation. In this research, I employed three distinct models to study how triggering TLRs contributes to ictogenesis. There is a correlation between developmental cortical malformations, e.g. focal cortical dysplasia (FCD), and fever-provoked, i.e. febrile, seizures in young children. Recently, neuroinflammation was reported in FCD lesions. Therefore, we posited that FCD-induced inflammation may increase seizure susceptibility (Chapter 2). To recapitulate FCD pathology, we induced a cortical freeze-lesion in neonatal rats. Lesioning the cortex triggered TLR4 downstream effectors, specifically the cytokine precursor Caspase-1, in the hippocampus ipsilateral to the lesion. Further, lesioned rats developed experimental febrile seizures markedly faster than sham control rats. Strikingly, blocking Caspase-1 activity prior to seizure induction significantly prolonged seizure latency in lesioned rats. Our results implicate Caspase-1-mediated inflammation as a main driver of febrile seizures in children with pre-existing brain malformations. In addition, previous reports determined that systemic activation of TLR4 cascade lowers seizure threshold. Hence, we developed an in vitro model to investigate whether penetration of peripheral immune cells into the brain during TLR4 stimulation promotes ictogenic activity (Chapter 3). First, we stimulated TLR4 pathway in leukocytes harvested from rat spleen, i.e. splenocytes. Thereafter, we co-cultured splenocytes with brain-derived organotypic slices in vitro. Adding TLR4-stimulated splenocytes gave rise to neuroinflammation and enhanced neuronal excitation, whereas adding unstimulated splenocytes failed to evoke pro-inflammatory or proexcitatory effects in organotypic slices. Moreover, Caspase-1 inhibition in organotypic slices cocultured with stimulated splenocytes diminished neuroinflammation and neuronal hyperexcitability. Our findings suggest that infiltration of TLR4-activated leukocytes into the brain elevate seizure predisposition via Caspase-1-mediated mechanisms. Beside TLR4 pathway, it was previously shown that activation of TLR3 signaling facilitates seizure evolution. In chapter 4, introducing a synthetic TLR3 agonist to mice in vivo and to hippocampal organotypic slices in vitro yielded anti-inflammatory mechanisms in a dose- and time-dependent manner. Also, we found that TLR3 stimulation suppressed hippocampal seizures in vivo and reduced synaptic excitability in the hippocampal network both in vivo and in vitro. Finally, we determined that TLR3-mediated anticonvulsive effects were chiefly driven by IRF3/IFN-β downstream cascades. Thus, our data suggests that TLR3 activation may protect the brain from seizures through production of IFN-β. Altogether, our findings provide insight into novel cellular mechanisms underlying inflammatory modulation of neural excitability. Furthermore, our discovery of the roles of Caspase-1 and IFN-β in influencing seizure threshold will improve our understanding of the molecular underpinnings of seizure generation, which may ultimately have therapeutic benefits for epilepsy treatment.

No description available.