Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts

DOI10.1137/19M1306154zbMath1475.05050OpenAlexW3198988513MaRDI QIDQ5157382

Seth Pettie, Shang-En Huang

Publication date: 18 October 2021

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

Full work available at URL: https://doi.org/10.1137/19m1306154

zbMATH Keywords

emulatorsadditive spannersshortcutting directed edges

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The convex hull of the integer points in a large ball
• Thorup-Zwick emulators are universally optimal hopsets
• Very Sparse Additive Spanners and Emulators
• Additive Spanners: A Simple Construction
• Additive spanners and (α, β)-spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Spanners and emulators with sublinear distance errors
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Better Distance Preservers and Additive Spanners
• Linear Size Distance Preservers
• The 4/3 Additive Spanner Exponent Is Tight
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Testing subgraphs in large graphs
• Shortcutting Planar Digraphs
• All-Pairs Almost Shortest Paths
• Efficient construction of directed hopsets and parallel approximate shortest paths
• Nearly work-efficient parallel algorithm for digraph reachability
• New Additive Spanners
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts