Next: Minimum Spanning Trees (min_span) Up: Graphs Algorithms Previous: Maximum Cardinality Matchings in

Maximum Weight Matchings in General Graphs (max_weight_matching)

list<edge> MAX_WEIGHT_MATCHING(graph G, edge_array<int> weights, bool checked=false)

MAX_WEIGHT_MATCHING takes as arguments an undirected graph G and an edge_array giving for each edge an integer (real) weight. It computes a maximum weighted matching of G, i.e., a set of edges M such that the sum of weights of all edges in M is maximal and no two edges in M share an end point. MAX_WEIGHT_MATCHING returns M as a list of edges. The algorithm ([23], [33], [49]) has running time O(|V| ^3). If checked=true then internally we ensure the correctness of the output at the cost of some runtime checking.

LEDA research project
1998-10-02

list<edge>	MAX_WEIGHT_MATCHING(graph G, edge_array<int> weights, bool checked=false)
		MAX_WEIGHT_MATCHING takes as arguments an undirected graph G and an edge_array giving for each edge an integer (real) weight. It computes a maximum weighted matching of G, i.e., a set of edges M such that the sum of weights of all edges in M is maximal and no two edges in M share an end point. MAX_WEIGHT_MATCHING returns M as a list of edges. The algorithm ([23], [33], [49]) has running time O(\|V\| ^3). If checked=true then internally we ensure the correctness of the output at the cost of some runtime checking.