or phenanthrene?
This is a “Pfaffian” orientation of G, in which every boun-dary face has an odd number of arcs oriented clockwise.
The node-node adjacency matrix of G will have the form
Here |det B| = 5 is the number of perfect matchings in G.
(This approach, with 1’s, works for any planar graph.)
FORMULATION OF THE BIPARTITE CARDINALITY MATCHING PROBLEM AS A MAX-FLOW PROBLEM
Corollary. In a bipartite graph, either there is a perfect matching or else there is a set of k nodes which are col-lectively adjacent to fewer than k nodes.
Running Time:
TWO-PHASE APPROACH
In the first phase, we run the shorest augmenting path algorithm until d(s) > n1/2 to quickly finds a good flow x.
In the second phase, we use Ford-Fulkerson to convert
x to a max-flow x*.
Note: If d(j) > n1/2, then node j will not occur in any subsequent augmenting paths. Thus each node is relabelled at most n1/2 times.
Time spent relabelling:
Number of augmentations:
Claim: After the first phase, the maximum (residual)
flow from s to t in G(x) is at most n1/2.
Running Time:
  
U V
Recall the shortest augmenting path algorithm for the max-flow problem maintains valid distance labels d(j), which satisfy d(i) d(j) +1 for all arcs (i,j) G(x).
S = { j N : d(j) > h } { j V : d(j) = h }
 
BIPARTITE MINIMUM COST MATCHINGS
The minimum cost perfect matching problem is just the assignment problem, and can be solved in O(n S(n,m,C)) time using the successive shortest paths algorithm.
To solve the minimum cost (or maximum weight) matching problem, we must add a dummy node before solving the minimum cost flow problem.
Do these approaches work for non-bipartite graphs?
Share with your friends: | 
