Best of two local models: centralized local and distributed local algorithms
DOI10.1016/j.ic.2018.07.001zbMath1401.68356arXiv1402.3796OpenAlexW2886624408MaRDI QIDQ1784947
Moti Medina, Dana Ron, Guy Even
Publication date: 27 September 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.3796
maximum matchinggraph algorithmsmaximum weighted matchingsublinear approximation algorithmscentralized local algorithmsdistributed local algorithms
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local computation algorithms for graphs of non-constant degrees
- Approximating weighted matchings in parallel
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Non-local probes do not help with many graph problems
- Fast primal-dual distributed algorithms for scheduling and matching problems
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- New techniques and tighter bounds for local computation algorithms
- Converting Online Algorithms to Local Computation Algorithms
- A Local Computation Approximation Scheme to Maximum Matching
- Survey of local algorithms
- Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
- Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
- Improved Distributed Approximate Matching
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Deterministic coin tossing with applications to optimal parallel list ranking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Some simple distributed algorithms for sparse networks
- Distributed (∆+1)-coloring in sublogarithmic rounds
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Best of two local models: centralized local and distributed local algorithms
