Distributed graph algorithms and their complexity: an introduction
From MaRDI portal
Publication:5135263
DOI10.4036/IIS.2015.L.04zbMATH Open1478.68445OpenAlexW2172696561MaRDI QIDQ5135263FDOQ5135263
Authors: 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)
Cites Work
- On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
- Distributed minimum cut approximation
- Optimal distributed all pairs shortest paths and applications
- Title not available (Why is that?)
- Distributed algorithms for network diameter and girth
- Design and Analysis of Distributed Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed verification and hardness of distributed approximation
- Distributed approximation algorithms for weighted shortest paths
- Networks cannot compute their diameter in sublinear time
- The Probabilistic Communication Complexity of Set Intersection
- Distributed computation in dynamic networks
- 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
- What cannot be computed locally!
- Distributed MST for constant diameter graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the distributional complexity of disjointness
- On the complexity of distributed graph coloring
- A fast and simple randomized parallel algorithm for maximal matching
- On the Complexity of Distributed Network Decomposition
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- On the distributed complexity of computing maximal matchings
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- Constant-time distributed dominating set approximation
- Survey of local algorithms
- Improved Distributed Approximate Matching
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- The locality of distributed symmetry breaking
- The price of being near-sighted
- Some simple distributed algorithms for sparse networks
- A fast distributed approximation algorithm for minimum spanning trees
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Distributed approximate matching
- Distributed Weighted Matching
- Efficient distributed computation of distance sketches in networks
- Aggregation in dynamic networks
- Invitation to discrete mathematics
- Efficient distributed source detection with limited bandwidth
- Weak models of distributed computing, with connections to modal logic
- Fast distributed computation in dynamic networks via random walks
- Distributed computation of the mode
Cited In (5)
- An introductory tutorial to concurrency-related distributed recursion
- Reducing conflict resolution time for solving graph problems in broadcast communications
- Distributed processing of graphs: Fundamental cycles algorithm
- Distributed graph algorithms for computer networks
- Low-complexity distributed algorithms on large-scale graphs: a brief review
This page was built for publication: Distributed graph algorithms and their complexity: an introduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5135263)
