next up previous contents index
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|3). 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