## Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Other editions - View all

### Common terms and phrases

adjacency list alternating path array augment the matching augmenting path base for Q base vertex Berge's lemma blossom edge bound called complete graph computes constructs a maximum contains the number Corollary cut vertex data structure decomposition defined Definition dummyedge dummyvertex edge uv edge xy Edmonds exit base exit deficit expansion step exposed vertex follows illustrated in Fig induction k-matching LASTA Lemma link path link step LINK(v linked blossom graph linked vertex linking edge links are assigned matched edge MATE MATE(v maximal blossom maximum cardinality matching maximum colink path maximum matching maximum weight colink maximum weight matching newbase newbase's NEXTA NEXTEDGE Note number of edges oldbase originally matched pair list pair step pointer link preorder list Proof random graphs recursive relinking REMATCH scans edge search graph Section shown in Fig slack step M2 subblossom subroutine Suppose Theorem unlinked UNPAIR Update weight colink path weighted graph weighted matching algorithm WMATCH