Graph spanners: A tutorial review
This survey provides a guiding reference to researchers seeking an overview of the large
body of literature about graph spanners. It surveys the current literature covering various …
body of literature about graph spanners. It surveys the current literature covering various …
Ultrasparse ultrasparsifiers and faster laplacian system solvers
A Jambulapati, A Sidford - ACM Transactions on Algorithms, 2021 - dl.acm.org
In this paper we provide an O (m loglog O (1) n log (1/ϵ))-expected time algorithm for solving
Laplacian systems on n-node m-edge graphs, improving upon the previous best expected …
Laplacian systems on n-node m-edge graphs, improving upon the previous best expected …
Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
M Parter - Proceedings of the 54th Annual ACM SIGACT …, 2022 - dl.acm.org
We (nearly) settle the time complexity for computing vertex fault-tolerant (VFT) spanners with
optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that …
optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that …
Optimal vertex fault-tolerant spanners in polynomial time
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant
spanners: for any positive integer k, every n-node graph has a (2 k–1)-spanner on O (f 1 …
spanners: for any positive integer k, every n-node graph has a (2 k–1)-spanner on O (f 1 …
Bridge girth: A unifying notion in network design
G Bodwin, G Hoppenworth… - 2023 IEEE 64th Annual …, 2023 - ieeexplore.ieee.org
A classic 1993 paper by Althöfer et al. proved a tight reduction from spanners, emulators,
and distance oracles to the extremal function γ of high-girth graphs. This paper initiated a …
and distance oracles to the extremal function γ of high-girth graphs. This paper initiated a …
Efficient and simple algorithms for fault-tolerant spanners
It was recently shown that a version of the greedy algorithm gives a construction of fault-
tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to …
tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to …
Labeled nearest neighbor search and metric spanners via locality sensitive orderings
A Filtser - arXiv preprint arXiv:2211.11846, 2022 - arxiv.org
Chan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive orderings (LSO)
for Euclidean space. A $(\tau,\rho) $-LSO is a collection $\Sigma $ of orderings such that for …
for Euclidean space. A $(\tau,\rho) $-LSO is a collection $\Sigma $ of orderings such that for …
Partially optimal edge fault-tolerant spanners
Recent work has established that, for every positive integer k, every n-node graph has a (2 k–
1)-spanner with O (f 1–1/kn 1+ 1/k) edges that is resilient to f edge or vertex faults. For vertex …
1)-spanner with O (f 1–1/kn 1+ 1/k) edges that is resilient to f edge or vertex faults. For vertex …
Vertex fault-tolerant emulators
A $ k $-spanner of a graph $ G $ is a sparse subgraph that preserves its shortest path
distances up to a multiplicative stretch factor of $ k $, and a $ k $-emulator is similar but not …
distances up to a multiplicative stretch factor of $ k $, and a $ k $-emulator is similar but not …
Locality-sensitive orderings and applications to reliable spanners
Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a
new tool that allows one to reduce problems in the Euclidean space ℝ d to the 1 …
new tool that allows one to reduce problems in the Euclidean space ℝ d to the 1 …