Fast parallel matching in expander graphs
Pierre Kelsen · 1993
Let H be a bipartite graph with bipartition (A, B) where IAI = n and every subset X of A with at most a n elements has at least blXl neighbors (a ~1, b > 1).We consider the problem of computing a matching from a given subset X ~A of size at most a n into l?.By Hall's theorem such a matchhg doea indeed exist.We propose two algorithms for this problem.The first algorithm is in NC for b ~d' for a constant e > O; here d denotes the maximum degree of a vertex in A. The second algorithm uses randomization and computes a matching for X provided b = 0(/-).It terminates in O(log n) steps for constant d and in Polylog(n) time for d = C@olylog(n))(with high probability).This algorithm is a local algorithm in the sense that the vertices in the graph establish the matching themselves in an online fashion.Both algorithms have applications to local and global routing in communication networks.In particular our results improve a construction of a self-routing nonblocking network by Arora, Leighton, and Maggs.