Source author record

Daniel Olah

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Sometimes Reliable Spanners of Almost Linear Size

Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, but this collateral damage is bounded by a fraction of the size of the attack. It is known that $Ω(n\log n)$ edges are needed to achieve this strong property, where $n$ is the number of vertices in the network, even in one dimension. Constructions of reliable geometric $(1+\varepsilon)$ -spanners, for $n$ points in $\Re^d$ , are known, where the resulting graph has $O( n \log n \log \log^{6}n )$ edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical -- replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip-list like construction. This results in a $1$ -spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in $\Re^d$ with $O( n \log \log^{2} n \log \log \log n )$ edges.

preprint2020arXiv

A Spanner for the Day After

We show how to construct $(1+\varepsilon)$ -spanner over a set $P$ of $n$ points in $\mathbb{R}^d$ that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $\vartheta,\varepsilon \in (0,1)$ , the computed spanner $G$ has $O\bigl(\varepsilon^{-c} \vartheta^{-6} n \log n (\log\log n)^6 \bigr)$ edges, where $c= O(d)$ . Furthermore, for any $k$ , and any deleted set $B \subseteq P$ of $k$ points, the residual graph $G \setminus B$ is $(1+\varepsilon)$ -spanner for all the points of $P$ except for $(1+\vartheta)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., $\vartheta$ ) 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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.