(1 + εΒ) -spanner constructions for general graphs

DOI10.1145/380752.380797zbMath1323.05118OpenAlexW2012245520MaRDI QIDQ5175965

Michael Elkin, David Peleg

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380797

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (max. 100)

Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Spanners for bounded tree-length graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ An approximation algorithm for the edge-dilation \(k\)-center problem. ⋮ Interval routing in reliability networks ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Network flow spanners ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: (1 + εΒ) -spanner constructions for general graphs