Matching
摘要
A matching of a graph is a subset of edges that do not share any endpoints. Matching can be used in many applications including channel frequency assignment in radio networks, graph partitioning, and clustering. In an unweighted graph, maximum matching of a graph is the set of edges that has the maximum cardinality among all matchings in that graph. In an edge-weighted weighted graph, our aim is to find a matching with the maximum (or minimum) total weight. Finding a maximum (weighted) matching in an unweighted or weighted graph is one of the rare graph problems that can be solved in polynomial time. We review sequential, parallel, and distributed algorithms for unweighted and weighted general graphs and bipartite graphs in this chapter.