The sparsest additive spanner via multiple weighted BFS trees (Q2201997): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2952039123
@@ Property / OpenAlex ID: W2952039123 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.01997
@@ Property / arXiv ID: 1811.01997 / rank @@
+Normal rank
@@ Property / cites work @@
+Error Amplification for Pairwise Spanner Lower Bounds
+Normal rank
@@ Property / cites work @@
+The 4/3 Additive Spanner Exponent Is Tight
@@ Property / cites work: The 4/3 Additive Spanner Exponent Is Tight / rank @@
+Normal rank
@@ Property / cites work @@
+Near-linear lower bounds for distributed distance computations, even in sparse networks
+Normal rank
@@ Property / cites work @@
+A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
+Normal rank
@@ Property / cites work @@
+A fast network-decomposition algorithm and its applications to constant-time distributed computation
+Normal rank
@@ Property / cites work @@
+Additive spanners and (α, β)-spanners
@@ Property / cites work: Additive spanners and (α, β)-spanners / rank @@
+Normal rank
@@ Property / cites work @@
+A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
+Normal rank
@@ Property / cites work @@
+Distributed exact weighted all-pairs shortest paths in near-linear time
+Normal rank
@@ Property / cites work @@
+Distributed Spanner Approximation
@@ Property / cites work: Distributed Spanner Approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Global computation in a poorly connected world
@@ Property / cites work: Global computation in a poorly connected world / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed construction of purely additive spanners
+Normal rank
@@ Property / cites work @@
+Compact routing schemes with improved stretch
@@ Property / cites work: Compact routing schemes with improved stretch / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Verification and Hardness of Distributed Approximation
+Normal rank
@@ Property / cites work @@
+Fast deterministic distributed algorithms for sparse spanners
+Normal rank
@@ Property / cites work @@
+Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
+Normal rank
@@ Property / cites work @@
+On the locality of distributed sparse spanner construction
+Normal rank
@@ Property / cites work @@
+Local Computation of Nearly Additive Spanners
@@ Property / cites work: Local Computation of Nearly Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
+Normal rank
@@ Property / cites work @@
+Computing almost shortest paths
@@ Property / cites work: Computing almost shortest paths / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed exact shortest paths in sublinear time
+Normal rank
@@ Property / cites work @@
+Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
+Normal rank
@@ Property / cites work @@
+A Distributed Algorithm for Minimum-Weight Spanning Trees
+Normal rank
@@ Property / cites work @@
+Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
+Normal rank
@@ Property / cites work @@
+Improved distributed algorithms for exact shortest paths
+Normal rank
@@ Property / cites work @@
+A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
+Normal rank
@@ Property / cites work @@
+Optimal distributed all pairs shortest paths and applications
+Normal rank
@@ Property / cites work @@
+New pairwise spanners
@@ Property / cites work: New pairwise spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Additive Spanners: A Simple Construction
@@ Property / cites work: Additive Spanners: A Simple Construction / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed distance computation and routing with small messages
+Normal rank
@@ Property / cites work @@
+Efficient distributed source detection with limited bandwidth
+Normal rank
@@ Property / cites work @@
+Improved Distributed Approximate Matching
@@ Property / cites work: Improved Distributed Approximate Matching / rank @@
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed approximation algorithms for weighted shortest paths
+Normal rank
@@ Property / cites work @@
+Vertex fault tolerant additive spanners
@@ Property / cites work: Vertex fault tolerant additive spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Congested Clique Algorithms for Graph Spanners
@@ Property / cites work: Congested Clique Algorithms for Graph Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Graph spanners
@@ Property / cites work: Graph spanners / rank @@
+Normal rank
@@ Property / cites work @@
+An Optimal Synchronizer for the Hypercube
@@ Property / cites work: An Optimal Synchronizer for the Hypercube / rank @@
+Normal rank
@@ Property / cites work @@
+A trade-off between space and efficiency for routing tables
+Normal rank
@@ Property / cites work @@
+Distributed algorithms for ultrasparse spanners and linear size skeletons
+Normal rank
@@ Property / cites work @@
+Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
+Normal rank
@@ Property / cites work @@
+Additive Spanners in Nearly Quadratic Time
@@ Property / cites work: Additive Spanners in Nearly Quadratic Time / rank @@
+Normal rank
@@ Property / cites work @@
+Improved deterministic distributed construction of spanners
+Normal rank