(1 + εΒ) -spanner constructions for general graphs
From MaRDI portal
Publication:5175965
DOI10.1145/380752.380797zbMath1323.05118MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
A Hierarchy of Lower Bounds for Sublinear Additive Spanners, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, Distributed algorithms for ultrasparse spanners and linear size skeletons, Approximating \(k\)-spanner problems for \(k>2\), An approximation algorithm for the edge-dilation \(k\)-center problem., Interval routing in reliability networks, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models, Spanners for bounded tree-length graphs, Network flow spanners, Multiplicative Approximations of Random Walk Transition Probabilities, Simple Distributed Spanners in Dense Congest Networks
Cites Work
