Light reliable spanners

DOI10.1137/25M1754662MaRDI QIDQ7395812zbMATH OpenFDO

Authors Arnold Filtser, Ofer Neiman

Publication date 2026

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/25M1754662

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68W99)

Cites work

• A data structure for dynamic trees
• A light metric spanner
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• A PTAS for subset TSP in minor-free graphs
• A spanner for the day after
• A subset spanner for Planar graphs, with application to subset TSP
• A tight bound on approximating arbitrary metrics by tree metrics
• A unified framework for light spanners
• Algorithms – ESA 2004
• An alternate proof of near-optimal light spanners
• Computing Lightweight Spanners Locally
• Constructing Light Spanners Deterministically in Near-Linear Time
• Distributed Construction of Light Networks
• Euclidean spanners in high dimensions
• Fault-tolerant geometric spanners
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
• Geometric Spanner Networks
• Graph spanners
• Graph spanners: a tutorial review
• Greedy spanners are optimal in doubling metrics
• scientific article; zbMATH DE number 1775395 (Why is no real title available?)
• scientific article; zbMATH DE number 1775403 (Why is no real title available?)
• scientific article; zbMATH DE number 7650073 (Why is no real title available?)
• Labeled nearest neighbor search and metric spanners via locality sensitive orderings
• Light spanners
• Light spanners for high dimensional norms via stochastic decompositions
• Locality-sensitive orderings and applications to reliable spanners
• Metric Embedding via Shortest Path Decompositions
• Minor-free graphs have light spanners
• Near-optimal light spanners
• New Doubling Spanners: Better and Simpler
• Object location using path separators
• On embedding trees into uniformly convex Banach spaces
• On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs
• On locality-sensitive orderings and their applications
• On metric Ramsey-type phenomena
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• On sparse spanners of weighted graphs
• Optimal fault-tolerant spanners in Euclidean and doubling metrics: breaking the ( n) lightness barrier
• Region-fault tolerant geometric spanners
• Reliable Spanners for Metric Spaces
• Robust geometric spanners
• Sometimes reliable spanners of almost linear size
• The greedy spanner is existentially optimal

This page was built for publication: Light reliable spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7395812)