$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs

DOI10.1137/S0097539701393384zbMath1056.05134OpenAlexW2042333226MaRDI QIDQ4651484

Michael Elkin, David Peleg

Publication date: 21 February 2005

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

Full work available at URL: https://doi.org/10.1137/s0097539701393384

zbMATH Keywords

graph algorithmsspannersgraph partitions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Source-wise round-trip spanners ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ Collective tree spanners in graphs with bounded parameters ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Covering metric spaces by few trees ⋮ Lossless Prioritized Embeddings ⋮ Deterministic improved round-trip spanners ⋮ On additive spanners in weighted graphs with local error ⋮ Demand-aware network designs of bounded degree ⋮ Vertex fault tolerant additive spanners ⋮ Improved weighted additive spanners ⋮ New pairwise spanners ⋮ Sublinear fully distributed partition with applications ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Combinatorial network abstraction by trees and distances ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Preprocess, set, query! ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ Approximating Shortest Paths in Graphs ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Unnamed Item ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Covering Metric Spaces by Few Trees ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners