Matching AlgorithmsWhat is a Matching in a graph?A matching in a graph G=(V,E) is a subset M of the edges E such that no two edges in M share a common end node.Which Matching Algorithms does LEDA provide?Bipartite Graphs: A graph is bipartite if it has two kinds of nodes and the edges are only allowed between nodes of different kind. Matching problems on bipartite graphs can be solved more efficiently than the corresponding problems on general graphs.
What is a Maximum Cardinality Matching, a Maximum Weighted Matching, and an Assignment?A maximum cardinality matching is a matching with a maximum number of edges. This is the most basic matching problem. In a maximum weighted matching the edges of the graph have weights and we want to find a matching with a maximum total weight, that is, the sum of the weights for the edges in the matching is maximum. An assignment in a bipartite graph is a matching such that each node in A and each node in B has an incident edge in the matching. A perfect matching in a graph is a matching such that each node is incident to an edge in the matching. |
See also:Manual Entries: Manual Page Maximum Cardinality Matchings in Bipartite Graphs Manual Page Bipartite Weighted Matchings and Assignments |