Distributed Graph Algorithms and their Complexity: An Introduction (Q5135263): Difference between revisions

@@ Property / cites work @@
+A fast and simple randomized parallel algorithm for the maximal independent set problem
+Normal rank
@@ Property / cites work @@
+Q4398822
@@ Property / cites work: Q4398822 / rank @@
+Normal rank
@@ Property / cites work @@
+On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
+Normal rank
@@ Property / cites work @@
+Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
+Normal rank
@@ Property / cites work @@
+The Locality of Distributed Symmetry Breaking
@@ Property / cites work: The Locality of Distributed Symmetry Breaking / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Aggregation in dynamic networks
@@ Property / cites work: Aggregation in dynamic networks / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient distributed computation of distance sketches in networks
+Normal rank
@@ Property / cites work @@
+Distributed Verification and Hardness of Distributed Approximation
+Normal rank
@@ Property / cites work @@
+Fast Distributed Computation in Dynamic Networks via Random Walks
+Normal rank
@@ Property / cites work @@
+Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
+Normal rank
@@ Property / cites work @@
+Q5743466
@@ Property / cites work: Q5743466 / rank @@
+Normal rank
@@ Property / cites work @@
+A Distributed Algorithm for Minimum-Weight Spanning Trees
+Normal rank
@@ Property / cites work @@
+A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
+Normal rank
@@ Property / cites work @@
+Distributed Minimum Cut Approximation
@@ Property / cites work: Distributed Minimum Cut Approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for local approximation
@@ Property / cites work: Lower bounds for local approximation / rank @@
+Normal rank
@@ Property / cites work @@
+On the Distributed Complexity of Computing Maximal Matchings
+Normal rank
@@ Property / cites work @@
+Weak models of distributed computing, with connections to modal logic
+Normal rank
@@ Property / cites work @@
+Optimal distributed all pairs shortest paths and applications
+Normal rank
@@ Property / cites work @@
+A fast and simple randomized parallel algorithm for maximal matching
+Normal rank
@@ Property / cites work @@
+The Probabilistic Communication Complexity of Set Intersection
+Normal rank
@@ Property / cites work @@
+A fast distributed approximation algorithm for minimum spanning trees
+Normal rank
@@ Property / cites work @@
+Distributed computation of the mode
@@ Property / cites work: Distributed computation of the mode / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed computation in dynamic networks
@@ Property / cites work: Distributed computation in dynamic networks / rank @@
+Normal rank
@@ Property / cites work @@
+What cannot be computed locally!
@@ Property / cites work: What cannot be computed locally! / rank @@
+Normal rank
@@ Property / cites work @@
+The price of being near-sighted
@@ Property / cites work: The price of being near-sighted / rank @@
+Normal rank
@@ Property / cites work @@
+Constant-time distributed dominating set approximation
+Normal rank
@@ Property / cites work @@
+On the complexity of distributed graph coloring
@@ Property / cites work: On the complexity of distributed graph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient distributed source detection with limited bandwidth
+Normal rank
@@ Property / cites work @@
+Locality in Distributed Graph Algorithms
@@ Property / cites work: Locality in Distributed Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Minimum-Weight Spanning Tree Construction in <i>O</i>(log log <i>n</i>) Communication Rounds
+Normal rank
@@ Property / cites work @@
+Distributed MST for constant diameter graphs
@@ Property / cites work: Distributed MST for constant diameter graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Distributed Approximate Matching
@@ Property / cites work: Improved Distributed Approximate Matching / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed approximate matching
@@ Property / cites work: Distributed approximate matching / rank @@
+Normal rank
@@ Property / cites work @@
+Q3126969
@@ Property / cites work: Q3126969 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3539854
@@ Property / cites work: Q3539854 / rank @@
+Normal rank
@@ Property / cites work @@
+Some simple distributed algorithms for sparse networks
+Normal rank
@@ Property / cites work @@
+Distributed approximation algorithms for weighted shortest paths
+Normal rank
@@ Property / cites work @@
+On the Complexity of Distributed Network Decomposition
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Distributed Algorithms for Network Diameter and Girth
+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 @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+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 @@
+Design and Analysis of Distributed Algorithms
@@ Property / cites work: Design and Analysis of Distributed Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Survey of local algorithms
@@ Property / cites work: Survey of local algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q4325545
@@ Property / cites work: Q4325545 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4782696
@@ Property / cites work: Q4782696 / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Weighted Matching
@@ Property / cites work: Distributed Weighted Matching / rank @@
+Normal rank