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.
翻译：由一套 $\ Disks $n$ 磁盘所引导的交叉图可以密度高。 因此, 在保存连接性的同时尝试和放大它是很自然的。 不幸的是, 稀有的图表总是可以通过去除少量的脊椎而断开的。 在这项工作中, 我们展示了一个在计算图中两个磁盘之间保持连接的垃圾化算法, 如果原始图形在从两个图形中移除任意的“ 攻击” 数据集$\ BSet\ subseteq \ Disks $之后仍然保持“ 连接 ” 。 因此, 新的稀有的图表与原始磁盘图具有相似的可靠性, 并且能够承受结点的灾难性故障, 同时仍然为其余的图形提供连接保证。 新图表具有接近线性的复杂性, 并且可以在接近线性的时间构造。 算法延伸到飞机上的任何形状的收藏, 其组合复杂性接近线性 。
相关内容
微信扫码咨询专知VIP会员