In this thesis we consider cutsets in graphs which can be expressed as unions of sets each of which is spanned by a tree of diameter at most d -- 1 for some integer d ≥ 1; we call these sets galaxy cutsets. These galaxy cutsets 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 also fail and cease to function. We approach our subject from four different points of view. We begin by exploring the connection between galaxies and a suitable type of flow, proving a min-max result for planar graphs. Then, after tackling the fundamental issue of recognising whether a 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 dual to the galaxies, and prove theta(log n) lower and upper approximability bounds for the problem of finding a maximum such flow. We then investigate the problem of network design, that is to say, the problem of constructing low cost spanning subgraphs of a given graph which are not vulnerable to cascading failures. Finally, we embark on a detailed analysis of the structure of star-cutsets in planar graphs and use our results to derive a polynomial time algorithm for the problem of neutralising every star-cutset by protecting edges.
展开▼
机译：在本文中，我们考虑图形中的割集，这些割集可以表示为集合的并集，对于某些整数d≥1，每个集合都由直径最大为d-1的树所跨越。我们称这些集合为银河割据。这些星系切割集既可以概括星形切割集，也可以推广顶点切割，并且可以作为简单的模型来对网络进行病毒式攻击或级联故障，其关键特性是受影响顶点的邻居也可能失效并停止运行。我们从四个不同的角度来探讨我们的主题。我们首先研究星系和合适类型的流之间的联系，证明平面图的最小-最大结果。然后，在解决了识别给定图是否易受病毒样攻击（即它是否包含星系割集）的基本问题之后，我们考虑对星系双重的流的加权形式，并证明theta（log n ）找到最大此类流量的问题的上下近似界限。然后，我们研究网络设计的问题，也就是说，构造给定图的低成本跨度子图的问题，该子图不易受到级联故障的影响。最后，我们开始对平面图中星形切割集的结构进行详细分析，并使用我们的结果来导出多项式时间算法，以解决通过保护边缘来中和每个星形切割集的问题。
展开▼
