A Hierarchy of Lower Bounds for Sublinear Additive Spanners

DOI10.1137/1.9781611974782.36zbMath1410.68265arXiv1607.07497OpenAlexW2951064515MaRDI QIDQ4575773

Greg Bodwin, Amir Abboud, Seth Pettie

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.07497

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Thorup-Zwick emulators are universally optimal hopsets ⋮ Improved weighted additive spanners ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ New Results on Linear Size Distance Preservers

This page was built for publication: A Hierarchy of Lower Bounds for Sublinear Additive Spanners