Distributed Maximum Matching in Bounded Degree Graphs
Guy Even, Moti Medina, Dana Ron · 2015
We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted case computes a matching whose size is at least (1−ϵ) times the optimal in Δ O(1/ϵ) + O(1/ϵ2) · log* (n) rounds where n is the number of vertices in the graph and Δ is the maximum degree. Our algorithm for the edge-weighted case computes a matching whose weight is at least (1 − ϵ) times the optimal in log(min{1/ωmin, n/ϵ})O(1/ϵ). (Δ O(1/ϵ) + log*(n)) rounds for edge-weights in [wmin, 1].