Lune

SODA2025Top-tier venue

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.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Having Hope in Hops: New Spanners, Preservers and Lower Bounds for HopsetsShimon Kogan, Merav ParterFOCS 2022 · 5 citations
  2. New (α, β) Spanners and HopsetsUri Ben-Levy, Merav ParterSODA 2020 · 10 citations
  3. Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallelMerav ParterSTOC 2022 · 8 citations
  4. Closing the Gap Between Directed Hopsets and Shortcut SetsAaron Bernstein, Nicole WeinSODA 2023 · 3 citations
  5. Deterministic Replacement Path CoveringKarthik C. S., Merav ParterSODA 2021 · 15 citations
Dusk over the sea between two cliffs drawn in fine vertical lines