Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets
Shimon Kogan, Merav Parter
Abstract
An r-missing spanner for a graph G is a sparse subgraph H ⊆ G satisfying that for any u, v pair there is a (possibly approximate) u-v shortest path P in G such that |P H| ≤ r. That is, H misses at most r edges from every u-v (approximate) shortest path. [Kogan and Parter, FOCS ’22] introduced the notion of missing spanners as an intermediate step for translating hopset constructions into spanners and distance preservers.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Having Hope in Hops: New Spanners, Preservers and Lower Bounds for HopsetsShimon Kogan, Merav ParterFOCS 2022 · 5 citations
- New (α, β) Spanners and HopsetsUri Ben-Levy, Merav ParterSODA 2020 · 10 citations
- Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallelMerav ParterSTOC 2022 · 8 citations
- Closing the Gap Between Directed Hopsets and Shortcut SetsAaron Bernstein, Nicole WeinSODA 2023 · 3 citations
- Deterministic Replacement Path CoveringKarthik C. S., Merav ParterSODA 2021 · 15 citations
