Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners

DOI10.1007/978-3-662-43951-7_49zbMath1411.05076arXiv1404.6835OpenAlexW2809995963MaRDI QIDQ5167871

Merav Parter

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

spannermetric embedding

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ New pairwise spanners ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ New Results on Linear Size Distance Preservers

Cites Work

• Unnamed Item
• Unnamed Item
• Ramsey partitions and proximity data structures
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• On sparse spanners of weighted graphs
• Spectral sparsification via random spanners
• Low distortion spanners
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• On Pairwise Spanners
• Undirected single-source shortest paths with positive integer weights in linear time
• Additive spanners and (α, β)-spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Approximate distance oracles
• Lower-stretch spanning trees
• Spanners and emulators with sublinear distance errors
• Graph spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Distributed Computing: A Locality-Sensitive Approach
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• An Optimal Synchronizer for the Hypercube
• All-Pairs Almost Shortest Paths
• Compact and localized distributed data structures
• Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
• Additive graph spanners
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Small Stretch Pairwise Spanners
• Distance Oracles beyond the Thorup--Zwick Bound
• Sparse Distance Preservers and Additive Spanners
• Automata, Languages and Programming
• New Additive Spanners
• Computing almost shortest paths