Efficient Distributed Algorithm for Maximum Matching in General Graphs

摘要

Let G = (V, E) be a finite, undirected, connected graph with the set of vertices V and the set of edges E. A matching M is a subset that no two edges of M are incident on a common vertex. A maximum matching is a matching of maximum cardinality. This thesis presents an efficient distributed algorithm for finding a maximum matching in a general graph. In designing his distributed matching algorithm, the author is concerned with the communication complexity. The maximum number of message transmissions determines the efficiency of the algorithm. He concentrates on minimizing the number of messages for two reasons. First, in an actual distributed system, the communication time would likely be much greater than the processing time. Second, in commercial computer networks, common carriers often charge by the number of packets or bits rather than by time.