Distributed Spanner Approximation (Q4997324): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Near-linear lower bounds for distributed distance computations, even in sparse networks
+Normal rank
@@ Property / cites work @@
+Routing with Polynomial Communication-Space Trade-Off
+Normal rank
@@ Property / cites work @@
+Hardness of Distributed Optimization
@@ Property / cites work: Hardness of Distributed Optimization / rank @@
+Normal rank
@@ Property / cites work @@
+A fast network-decomposition algorithm and its applications to constant-time distributed computation
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles for unweighted graphs in expected             <i>O</i>             (             <i>n</i>             <sup>2</sup>             ) time
+Normal rank
@@ Property / cites work @@
+A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for spanner problems and directed Steiner forest
+Normal rank
@@ Property / cites work @@
+Finding sparser directed spanners
@@ Property / cites work: Finding sparser directed spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed construction of purely additive spanners
+Normal rank
@@ Property / cites work @@
+An optimal distributed (Δ+1)-coloring algorithm?
@@ Property / cites work: An optimal distributed (Δ+1)-coloring algorithm? / rank @@
+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 @@
+Q2969610
@@ Property / cites work: Q2969610 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+On the locality of distributed sparse spanner construction
+Normal rank
@@ Property / cites work @@
+Sublinear fully distributed partition with applications
+Normal rank
@@ Property / cites work @@
+Label Cover Instances with Large Girth and the Hardness of Approximating Basic             <i>k</i>             -Spanner
+Normal rank
@@ Property / cites work @@
+Directed spanners via flow-based linear programs
@@ Property / cites work: Directed spanners via flow-based linear programs / rank @@
+Normal rank
@@ Property / cites work @@
+Fault-tolerant spanners
@@ Property / cites work: Fault-tolerant spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Distance-Bounded Network Design Through Distributed Convex Programming
+Normal rank
@@ Property / cites work @@
+Approximating Low-Stretch Spanners
@@ Property / cites work: Approximating Low-Stretch Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
+Normal rank
@@ Property / cites work @@
+On the power of the congested clique model
@@ Property / cites work: On the power of the congested clique model / rank @@
+Normal rank
@@ Property / cites work @@
+Computing almost shortest paths
@@ Property / cites work: Computing almost shortest paths / rank @@
+Normal rank
@@ Property / cites work @@
+An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
+Normal rank
@@ Property / cites work @@
+A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
+Normal rank
@@ Property / cites work @@
+Approximating \(k\)-spanner problems for \(k>2\)
@@ Property / cites work: Approximating \(k\)-spanner problems for \(k>2\) / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of approximating spanner problems
@@ Property / cites work: The hardness of approximating spanner problems / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
+Normal rank
@@ Property / cites work @@
+Q5543308
@@ Property / cites work: Q5543308 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743466
@@ Property / cites work: Q5743466 / rank @@
+Normal rank
@@ Property / cites work @@
+A Fast Parametric Maximum Flow Algorithm and Applications
+Normal rank
@@ Property / cites work @@
+Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
+Normal rank
@@ Property / cites work @@
+Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
+Normal rank
@@ Property / cites work @@
+On the complexity of local distributed graph problems
+Normal rank
@@ Property / cites work @@
+Distributed (∆+1)-coloring in sublogarithmic rounds
+Normal rank
@@ Property / cites work @@
+Optimal distributed all pairs shortest paths and applications
+Normal rank
@@ Property / cites work @@
+An efficient distributed algorithm for constructing small dominating sets
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating spanners
@@ Property / cites work: On the hardness of approximating spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Generating Sparse 2-Spanners
@@ Property / cites work: Generating Sparse 2-Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Generating Low-Degree 2-Spanners
@@ Property / cites work: Generating Low-Degree 2-Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Local Computation
@@ Property / cites work: Local Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Constant-time distributed dominating set approximation
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+A new series of dense graphs of high girth
@@ Property / cites work: A new series of dense graphs of high girth / rank @@
+Normal rank
@@ Property / cites work @@
+Locality in Distributed Graph Algorithms
@@ Property / cites work: Locality in Distributed Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Low diameter graph decompositions
@@ Property / cites work: Low diameter graph decompositions / rank @@
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
+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 @@
+Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
+Normal rank
@@ Property / cites work @@
+On the distributional complexity of disjointness
@@ Property / cites work: On the distributional complexity of disjointness / rank @@
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Roundtrip spanners and roundtrip routing in directed graphs
+Normal rank
@@ Property / cites work @@
+Polylogarithmic-time deterministic network decomposition and distributed derandomization
+Normal rank
@@ Property / cites work @@
+Distributed Verification and Hardness of Distributed Approximation
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles
@@ Property / cites work: Approximate distance oracles / rank @@
+Normal rank