We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge. A sampling of our end results is as follows. -- An @math -round deterministic distributed algorithm for computing a maximal matching, in @math -node graphs with maximum degree @math . This is the first improvement in about 20 years over the celebrated @math -round algorithm of Hanckowiak, Karonski, and Panconesi [SODA'98, PODC'99]. -- A deterministic distributed algorithm for computing a @math -approximation of maximum matching in @math rounds. This is exponentially faster than the classic @math -round @math -approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an @math -maximal matching which leaves only an @math -fraction of the edges on unmatched nodes. -- An @math -round deterministic distributed algorithm for computing a @math -approximation of a maximum weighted matching, and also for the more general problem of maximum weighted @math -matching. These improve over the @math -round @math -approximation algorithm of Panconesi and Sozio [DIST'10], where @math denotes the maximum normalized weight.
This paper deals with distributed graph algorithms. Processors reside in the vertices of a graph G and communicate only with their neighbors. The system is synchronous and reliable, there is no limit on message lengths and local computation is instantaneous. The results: A maximal independent set in an n-cycle cannot be found faster than Ω(log* n) and this is optimal by [CV]. The d-regular tree of radius r cannot be colored with fewer than √d colors in time 2r 3. If Δ is the largest degree in G which has order n, then in time O(log*n) it can be colored with O(Δ2) colors.