Next: Minimum Spanning Trees ( Up: Graph Algorithms Previous: Maximum Cardinality Matchings in Contents Index

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|³). If checked=true then internally we ensure the correctness of the output at the cost of some runtime checking.

LEDA research project
2000-02-09

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\|³). If checked=true then internally we ensure the correctness of the output at the cost of some runtime checking.