In this thesis we consider cutsets in graphs which can be expressed as unionsof sets each of which is spanned by a tree of diameter at most d-1 for someinteger d ≥ 1; we call these sets galaxy cutsets. These galaxycutsets generalise both star-cutsets and vertex-cuts, and serve as simple models for virus-like attacks on or cascading failures in networks,the crucial property being that neighbours of affected vertices may alsofail and cease to function. We approach our subject from four different pointsof view. We begin by exploring the connection between galaxiesand a suitable type of flow, proving a min-max result for planargraphs. Then, after tackling the fundamental issue of recognising whethera given graph is susceptible to virus-like attacks, i.e. whether it contains a galaxy cutset, we consider a weighted version of the flows that are dualto the galaxies, and prove Θ(log n) lower and upper approximability boundsfor the problem of finding a maximum such flow. We then investigate the problem of network design, that is tosay, the problem of constructing low cost spanning subgraphs of a given graph which are not vulnerable to cascading failures. Finally, weembark on a detailed analysis of the structure of star-cutsets in planar graphs and useour results to derive a polynomial time algorithm for the problem ofneutralising every star-cutset by protecting edges. / Dans cette thèse, nous considerons des séparateurs dans les graphes qui peuvent être éxprimés sous forme d'une union d'ensembles de sommets dans laquelle chaque ensemble est couvert par un arbre de diamètre d-1 pour un nombre entier d ≥ 1; nous appellons ces séparateurs des galaxies séparatrices. Les galaxies séparatrices genéralisent les étoiles séparatrices et les séparateurs formés par un ensemble de sommets, et elles servent comme simple modèle pour des attaques de virus sur ou des cascades de défaillances dans un réseau, la proprieté distinguante étant que les voisins des sommets qui sont affectés peuvent eux aussi faillir. Nous approchons le sujet depuis quatre points de vue différents. Nous commençons par explorer le lien entre les galaxies et un type de flot approprié, et nous prouvons un résultat de type min max pour les graphes planaires. Ensuite, après avoir résolu la question fondamentale de reconnaitre si un graphe donné est sensible aux attaques de virus, c'est-à-dire s'il contient une galaxie séparatrice, nous introduisons des capacités dans les flots correspondants aux galaxies, et demontrons une borne d'approximabilité inférieure et supérieure de Θ(log n)pour le problème de trouver un flot maximum. Ensuite, nous enquêtons sur le problème de dessein de réseau, c'est-à-dire le problème de construire des sous-graphes couvrants peu coûteux qui ne sont pas sensibles aux cascades de défaillances. Finalement, nous nous lançons dans une analyse détaillée de la structure des étoiles séparatrices dans les graphes planaires, et nous utilisons nos résultats pour développer un algorithme polynomial qui résout le problème de neutraliser toutes les étoiles séparatrices en protégeant des arêtes.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.97002 |
| Date | January 2011 |
| Creators | Sonnerat, Nicolas |
| Contributors | Adrian Roshan Vetta (Internal/Supervisor), Bruce Alan Reed (Internal/Cosupervisor2) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0014 seconds