Distributed Graph Algorithms and their Complexity: An Introduction

DOI10.4036/iis.2015.L.04zbMath1478.68445OpenAlexW2172696561MaRDI QIDQ5135263

Taisuke Izumi

Publication date: 19 November 2020

Published in: Interdisciplinary Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4036/iis.2015.l.04

zbMATH Keywords

computational complexitygraph algorithmsdistributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Cites Work

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

This page was built for publication: Distributed Graph Algorithms and their Complexity: An Introduction