Cover Image

Almost-Optimal Sublinear Additive Spanners

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tan, Zihan, Zhang, Tianyi
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
by: He, Jialin, et al.
Published: (2025)

Multiplicative Spanners in Minor-Free Graphs
by: Bodwin, Greg, et al.
Published: (2025)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Lightweight Near-Additive Spanners
by: Gitlitz, Yuval, et al.
Published: (2024)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
by: Qi, Chuhan
Published: (2025)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
by: Ahmed, Reyan, et al.
Published: (2024)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
by: La, An, et al.
Published: (2025)

Towards Instance-Optimal Euclidean Spanners
by: Le, Hung, et al.
Published: (2024)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

Routing-Controlled Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Directed Buy-at-Bulk Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

Minimum Temporal Spanners in Happy Graphs
by: Casteigts, Arnaud, et al.
Published: (2026)

Graph Spanners for Group Steiner Distances
by: Bilò, Davide, et al.
Published: (2024)

A Unified Framework for Hopsets and Spanners
by: Neiman, Ofer, et al.
Published: (2021)

Shortcuts and Transitive-Closure Spanners Approximation
by: Chalermsook, Parinya, et al.
Published: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Expander Decomposition with Almost Optimal Overhead
by: Bansal, Nikhil, et al.
Published: (2026)

Paths and Intersections: Exact Emulators for Planar Graphs
by: Li, George Z., et al.
Published: (2025)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
by: Ghaffari, Mohsen, et al.
Published: (2025)

A Simple Dynamic Spanner via APSP
by: Kyng, Rasmus, et al.
Published: (2024)

Greedy Completion for Weighted $(α,β)$-Spanners
by: Tzalik, Elad
Published: (2026)

An Alternate Proof of Near-Optimal Light Spanners
by: Bodwin, Greg
Published: (2023)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

The Complexity of Geodesic Spanners
by: de Berg, Sarita, et al.
Published: (2023)

Optimal Scalarizations for Sublinear Hypervolume Regret
by: Zhang, Qiuyi
Published: (2023)

Computing String Covers in Sublinear Time
by: Radoszewski, Jakub, et al.
Published: (2024)

On Solving Linear Systems in Sublinear Time
by: Andoni, Alexandr, et al.
Published: (2018)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
by: Caporrella, Matteo, et al.
Published: (2026)

Sublinear Algorithms for TSP via Path Covers
by: Behnezhad, Soheil, et al.
Published: (2023)

Counting Distinct Square Substrings in Sublinear Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Sublinear Spectral Clustering Oracle with Little Memory
by: Shen, Ranran, et al.
Published: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Approximate Butterfly Counting in Sublinear Time
by: Luo, Chi, et al.
Published: (2026)