A note on distance-preserving graph sparsification

DOI10.1016/j.ipl.2021.106205OpenAlexW3199376991MaRDI QIDQ2059887

Greg Bodwin

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial problemstheory of computationspannersdistance preserversreachability preservers

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

On additive spanners in weighted graphs with local error ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms

Cites Work

• Unnamed Item
• New pairwise spanners
• Graph spanners: a tutorial review
• On Sketching Quadratic Forms
• On Pairwise Spanners
• Additive Spanners: A Simple Construction
• Additive spanners and (α, β)-spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Small Stretch Pairwise Spanners and Approximate $D$-Preservers
• Error Amplification for Pairwise Spanner Lower Bounds
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• A trade-off between space and efficiency for routing tables
• Compact routing with slack in low doubling dimension
• Compact routing with slack
• Spanners with Slack
• New Additive Spanners

This page was built for publication: A note on distance-preserving graph sparsification