Distributed spanner approximation
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 6696497 (Why is no real title available?)
- scientific article; zbMATH DE number 3258067 (Why is no real title available?)
- A Fast Parametric Maximum Flow Algorithm and Applications
- A Greedy Heuristic for the Set-Covering Problem
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- A new series of dense graphs of high girth
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- An efficient distributed algorithm for constructing small dominating sets
- An optimal distributed (+1)-coloring algorithm?
- Approximate distance oracles
- Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
- Approximating \(k\)-spanner problems for \(k>2\)
- Approximating low-stretch spanners
- Approximating spanners and directed Steiner forest: upper and lower bounds
- Approximation algorithms for combinatorial problems
- Approximation algorithms for spanner problems and directed Steiner forest
- Automata, Languages and Programming
- Communication Complexity
- Compact routing schemes with improved stretch
- Computing almost shortest paths
- Constant-time distributed dominating set approximation
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Directed spanners via flow-based linear programs
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- Distributed Computing: A Locality-Sensitive Approach
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Distributed distance-bounded network design through distributed convex programming
- Distributed verification and hardness of distributed approximation
- Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models
- Efficient algorithms for constructing very sparse spanners and emulators
- Efficient algorithms for constructing very sparse spanners and emulators
- Fault-tolerant spanners
- Finding sparser directed spanners
- Generating Low-Degree 2-Spanners
- Generating Sparse 2-Spanners
- Graph spanners
- Hardness of Distributed Optimization
- Improved deterministic distributed construction of spanners
- Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- Local computation: lower and upper bounds
- Locality in Distributed Graph Algorithms
- Low diameter graph decompositions
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- Near-optimal distributed approximation of minimum-weight connected dominating set
- Networks cannot compute their diameter in sublinear time
- On the complexity of local distributed graph problems
- On the distributional complexity of disjointness
- On the hardness of approximating spanners
- On the locality of distributed sparse spanner construction
- On the power of the congested clique model
- On the ratio of optimal integral and fractional covers
- Optimal distributed all pairs shortest paths and applications
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Quadratic and near-quadratic lower bounds for the CONGEST model
- Roundtrip spanners and roundtrip routing in directed graphs
- Routing with Polynomial Communication-Space Trade-Off
- Sublinear fully distributed partition with applications
- The hardness of approximating spanner problems
Cited in
(10)- Sparser: A Paradigm for Running Distributed Algorithms
- Distributed construction of low-interference spanners
- Distributed Approximation Algorithm for Resource Clustering
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- An efficient distributed algorithm for canonical labeling on directed split-stars
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- Distributed Spanner Approximation
- Distributed distance-bounded network design through distributed convex programming
- scientific article; zbMATH DE number 2036580 (Why is no real title available?)
- Distribution-sensitive construction of the greedy spanner
This page was built for publication: Distributed spanner approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997324)
