next up previous contents
Next: Maximum Cardinality Matchings in Up: Graphs Algorithms Previous: Maximum Cardinality Matchings in

   
Bipartite Weighted Matchings and Assignments (mwb_matching)

We give functions for computing maximum and minimum weighted matchings in bipartite graphs. All functions provide a proof of optimality of their answer in the form of a potential function pot (all functions below are also available without the parameter pot). See the LEDA book for a discussion of potential functions.

The functions in this section are template functions. The template parameter NT can be instantiated with any number type. In order to use the template version of the function the appropriate .t-file must be included. #include <LEDA/templates/mwb_matching.t>

The pre-instantiated versions have the same function names except for the suffix _T. Preinstatiations are available for the number types int and double. In order to use them either

#include <LEDA/mwb_matching.h>

or

#include <LEDA/graph_alg.h>

has to be included (the latter file includes the former).

Special care should be taken when using the functions with a number type NT that can incur rounding error, e.g., the type double. The functions are only guaranteed to perform correctly if all arithmetic performed is without rounding error. This is the case if all numerical values in the input are integers (albeit stored as a number of type NT) and if none of the intermediate results exceeds the maximal integer representable by the number type (2^52 in the case of doubles). All intermediate results are sums and differences of input values, in particular, the algorithms do not use divisions and multiplications.

The algorithms have the following arithmetic demands. Let C be the maximal absolute value of any edge cost and let k = min(|A|,|B|).

All intermediate values are bounded by 3C in the case of maximum weight matchings, by 7C + 14kC in the case of the assignment algorithm, and by 3(C + 1 + 2kC) in the case of maximum weight matchings of maximum cardinality.

list<edge> MAX_WEIGHT_BIPARTITE_MATCHING_T(graph& G, edge_array<NT> c, node_array<NT>& pot)
    computes a matching of maximal cost and a potential function pot that is tight with respect to M. The running time of the algorithm is O(n* (m + n log n)).
Precondition: G must be bipartite.


list<edge> MAX_WEIGHT_BIPARTITE_MATCHING_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot)
    As above. It is assumed that the partition (A, B) witnesses that G is bipartite and that all edges of G are directed from A to B. If A and B have different sizes then is is advisable that A is the smaller set; in general, this leads to smaller running time.


void CHECK_MWBM_T(graph G, edge_array<NT> c, list<edge> M, node_array<NT> pot)
    checks that pot is a tight feasible potential function with respect to M and that M is a matching. Tightness of pot implies that M is a maximum weighted matching.


list<edge> MAX_WEIGHT_ASSIGNMENT_T(graph& G, edge_array<NT> c, node_array<NT>& pot)
    computes a perfect matching of maximal cost and a potential function pot that is tight with respect to M. The running time of the algorithm is O(n* (m + n log n)). If G contains no perfect matching the empty set of edges is returned.
Precondition: G must be bipartite.


list<edge> MAX_WEIGHT_ASSIGNMENT_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot)
    As above. It is assumed that the partition (A, B) witnesses that G is bipartite and that all edges of G are directed from A to B.


void CHECK_MAX_WEIGHT_ASSIGNMENT_T(graph G, edge_array<NT> c, list<edge> M, node_array<NT> pot)
    checks that pot is a tight feasible potential function with respect to M and that M is a perfect matching. Tightness of pot implies that M is a maximum cost assignment.


list<edge> MIN_WEIGHT_ASSIGNMENT_T(graph& G, edge_array<NT> c, node_array<NT>& pot)
    computes a perfect matching of minimal cost and a potential function pot that is tight with respect to M. The running time of the algorithm is O(n* (m + n log n)). If G contains no perfect matching the empty set of edges is returned.
Precondition: G must be bipartite.


list<edge> MIN_WEIGHT_ASSIGNMENT_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot)
    As above. It is assumed that the partition (A, B) witnesses that G is bipartite and that all edges of G are directed from A to B.


void CHECK_MIN_WEIGHT_ASSIGNMENT_T(graph G, edge_array<NT> c, list<edge> M, node_array<NT> pot)
    checks that pot is a tight feasible potential function with respect to M and that M is a perfect matching. Tightness of pot implies that M is a minimum cost assignment.


list<edge> MWMCB_MATCHING_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot)
    Returns a maximum weight matching among the matching of maximum cardinality. The potential function pot is tight with respect to a modified cost function which increases the cost of every edge by L = 1 + 2kC where C is the maximum absolute value of any weight and k = min(|A|,|B|). It is assumed that the partition (A, B) witnesses that G is bipartite and that all edges of G are directed from A to B. If A and B have different sizes, it is advisable that A is the smaller set; in general, this leads to smaller running time.



next up previous contents
Next: Maximum Cardinality Matchings in Up: Graphs Algorithms Previous: Maximum Cardinality Matchings in
LEDA research project
1998-10-02