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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Matching

  • K. Erciyes

摘要

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.