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

DOI10.1007/978-3-662-43951-7_49zbMath1411.05076arXiv1404.6835MaRDI 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

spanner; metric embedding

Mathematics Subject Classification ID

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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