(1 + εΒ) -spanner constructions for general graphs
From MaRDI portal
Publication:5175965
DOI10.1145/380752.380797zbMath1323.05118OpenAlexW2012245520MaRDI QIDQ5175965
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
Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (12)
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
This page was built for publication: (1 + εΒ) -spanner constructions for general graphs