文章基本信息

标题：A Spanner for the Day After
本地全文：下载
作者：Kevin Buchin ; Sariel Har-Peled ; D{'a}niel Ol{'a}h 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：129
页码：1-15
DOI：10.4230/LIPIcs.SoCG.2019.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We show how to construct (1+epsilon)-spanner over a set P of n points in R^d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters theta, epsilon in (0,1), the computed spanner G has O(epsilon^{-7d} log^7 epsilon^{-1} * theta^{-6} n log n (log log n)^6) edges. Furthermore, for any k, and any deleted set B subseteq P of k points, the residual graph G B is (1+epsilon)-spanner for all the points of P except for (1+theta)k of them. No previous constructions, beyond the trivial clique with O(n^2) edges, were known such that only a tiny additional fraction (i.e., theta) lose their distance preserving connectivity. Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one dimensional construction in a black box fashion.
关键词：Geometric spanners; vertex failures; robustness