Next: Minimum Spanning Trees ( Up: Graph Algorithms Previous: General Weighted Matchings (   Contents   Index

# Stable Matching ( stable_matching )

We are given a bipartite graph G = (A B, E) in which the edges incident to every vertex are linearly ordered. The order expresses preferences. A matching M in G is stable if there is no pair (a, b) E M such that (1) a is unmatched or prefers b over its partner in M and (2) b is unmatched or prefers a over its partner in M . In such a situation a has the intention to switch to b and b has the intention to switch to a , i.e., the pairing is unstable.
We provide a function to compute a correct input graph from the preference data, a function that computes the stable matching when the graph is given and a function that checks whether a given matching is stable.

 void StableMatching(const graph& G, const list< node> & A, const list< node> & B, list< edge> & M) The function takes a bipartite graph G with sides A and B and computes a maximal stable matching M which is A -optimal. The graph is assumed to be bidirected, i.e, for each (a, b) E we also have (b, a) E . It is assumed that adjacency lists record the preferences of the vertices. The running time is O(n + m) . Precondition The graph G is bidirected and a map. Sets A and B only contain nodes of graph G . In addition they are disjoint from each other. bool CheckStableMatching(const graph& G, const list< node> & A, const list< node> & B, const list< edge> & M) returns true if M is a stable matching in G . The running time is O(n + m) . Precondition A and B only contain nodes from G . The graph G is bipartite with respect to lists A and B . void CreateInputGraph(graph& G, list< node> & A, list< node> & B, node_map< int> & nodes_a, node_map< int> & nodes_b, const list< int> & InputA, const list< int> & InputB, const map< int, list< int> > & preferencesA, const map< int, list< int> > & preferencesB) The function takes a list of objects InputA and a list of objects InputB . The objects are represented bei integer numbers, multiple occurences of the same number in the same list are ignored. The maps preferencesA and preferencesB give for each object i the list of partner candidates with respect to a matching. The lists are decreasingly ordered according to the preferences. The function computes the input data G , A and B for calling the function StableMatching(constgraph&,...) . The maps nodesa and nodesb provide the objects in A and B corresponding to the nodes in the graph. Precondition The entries in the lists in the preference maps only contain elements from InputB resp. InputA . There are no multiple occurences of an element in the same such list.

Next: Minimum Spanning Trees ( Up: Graph Algorithms Previous: General Weighted Matchings (   Contents   Index
Christian Uhrig 2017-04-07