New Results on Linear Size Distance Preservers

DOI10.1137/19M123662XMaRDI QIDQ5858650

Greg Bodwin

Publication date: 14 April 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph spannersshortest pathsextremal graph theorydistance preservers

Mathematics Subject Classification ID

Computer science (68-XX) Combinatorics (05-XX)

Related Items (2)

Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Multi-priority graph sparsification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new proof of the graph removal lemma
• Extremal problems in discrete geometry
• The convex hull of the integer points in a large ball
• Thorup-Zwick emulators are universally optimal hopsets
• New pairwise spanners
• An improved construction of progression-free sets
• Terminal embeddings
• Dual Failure Resilient BFS Structure
• Sparse Fault-Tolerant BFS Trees
• Graph removal lemmas
• On Pairwise Spanners
• Very Sparse Additive Spanners and Emulators
• Sparse Sourcewise and Pairwise Distance Preservers
• Small Stretch Pairwise Spanners and Approximate $D$-Preservers
• Error Amplification for Pairwise Spanner Lower Bounds
• Better Distance Preservers and Additive Spanners
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• The 4/3 Additive Spanner Exponent Is Tight
• Testing subgraphs in large graphs
• A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
• Multiple Source Dual Fault Tolerant BFS Trees
• Distance-Preserving Subgraphs of Interval Graphs
• Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
• On the Structure of Unique Shortest Paths in Graphs
• Low Distortion Spanners
• Sparse Distance Preservers and Additive Spanners
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: New Results on Linear Size Distance Preservers