On additive spanners in weighted graphs with local error

DOI10.1007/978-3-030-86838-3_28OpenAlexW3202764849MaRDI QIDQ2672448

Reyan Ahmed, Richard Spence, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov

Publication date: 8 June 2022

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Improved weighted additive spanners ⋮ Multi-priority graph sparsification

Cites Work

• New pairwise spanners
• Balancing minimum spanning trees and shortest-path trees
• Graph spanners: a tutorial review
• A note on distance-preserving graph sparsification
• Weighted additive spanners
• Low distortion spanners
• On Pairwise Spanners
• Additive Spanners: A Simple Construction
• Additive spanners and (α, β)-spanners
• Small Stretch Pairwise Spanners and Approximate $D$-Preservers
• Additive Spanners in Nearly Quadratic Time
• Graph spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Computing Visibility Information in an Inaccurate Simple Polygon
• Near-Optimal Light Spanners
• The 4/3 Additive Spanner Exponent Is Tight
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• A trade-off between space and efficiency for routing tables
• All-Pairs Almost Shortest Paths
• Generating sparse spanners for weighted graphs
• Light Spanners
• The Greedy Spanner is Existentially Optimal
• New Additive Spanners
• Distributed construction of purely additive spanners