Improved deterministic distributed matching via rounding

DOI10.1007/s00446-018-0344-4zbMath1445.68335arXiv1703.00900OpenAlexW2748046883WikidataQ129148605 ScholiaQ129148605MaRDI QIDQ2189173

Manuela Fischer

Publication date: 15 June 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.00900

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Related Items (5)

Node and edge averaged complexities of local graph problems ⋮ Distributed half-integral matching and beyond ⋮ Distributed half-integral matching and beyond ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Distributed backup placement

Cites Work

• Unnamed Item
• Distributed algorithms for covering, packing and maximum weighted matching
• An improved parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• Julius Petersen's theory of regular graphs
• Distributed algorithm for approximating the maximum matching
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• On the Distributed Complexity of Computing Maximal Matchings
• Distributed maximal matching
• A faster distributed algorithm for computing maximal matchings deterministically
• Linear-in-delta lower bounds in the LOCAL model
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Improved Distributed Approximate Matching
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Edge Dominating Sets in Graphs
• Locality in Distributed Graph Algorithms
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed Degree Splitting, Edge Coloring, and Orientations
• On the complexity of local distributed graph problems
• Some simple distributed algorithms for sparse networks
• Distributed algorithms for edge dominating sets
• Distributed (∆+1)-coloring in sublogarithmic rounds
• Brief Announcement
• Distributed approximate matching
• Distributed Weighted Matching
• Algorithms – ESA 2004
• What cannot be computed locally!

This page was built for publication: Improved deterministic distributed matching via rounding