论文标题
可靠连接性的稀疏磁盘交叉图
Sparsifying Disk Intersection Graphs for Reliable Connectivity
论文作者
论文摘要
由$ n $磁盘的集合$ \磁盘$引起的相交图可能是密集的。因此，在保持连通性的同时，尝试稀疏它是很自然的。不幸的是，始终可以通过删除少量顶点来断开稀疏图。在这项工作中，我们提出了一种稀疏算法，即使原始图保持````the offeration）''''在计算图中的两个磁盘之间保持连接性，如果原始图保持````良好'''''''''''''''设置$ \ bset \ bset \ subseteq \ subseteq \ disks $即使在两个图中。因此，新的稀疏图与原始磁盘图具有相似的可靠性，并且可以承受节点的灾难性故障，同时仍为其余图提供连接保证。新图具有接近线性的复杂性，可以在几乎线性时间内构造。 该算法扩展到平面中的任何形状集合，使它们的联合复杂性接近线性。
The intersection graph induced by a set $\Disks$ of $n$ disks can be dense. It is thus natural to try and sparsify it, while preserving connectivity. Unfortunately, sparse graphs can always be made disconnected by removing a small number of vertices. In this work, we present a sparsification algorithm that maintains connectivity between two disks in the computed graph, if the original graph remains ``well-connected'' even after removing an arbitrary ``attack'' set $\BSet \subseteq \Disks$ from both graphs. Thus, the new sparse graph has similar reliability to the original disk graph, and can withstand catastrophic failure of nodes while still providing a connectivity guarantee for the remaining graph. The new graphs has near linear complexity, and can be constructed in near linear time. The algorithm extends to any collection of shapes in the plane, such that their union complexity is near linear.
