Unique maximum matching algorithms

We consider the problem of testing the uniqueness of maximum matchings, bot h in the unweighted and in the weighted case. For the unweighted case, we h ave two results, First, given a graph with n vertices and in edges, we can test whether the graph has a unique perfect matching, and find it if it exi sts, in O(m log(4) n) time. This algorithm uses a recent dynamic connectivi ty algorithm and an old result of Kotzig characterizing unique perfect matc hings in terms of bridges. For the special case of planar graphs, we improv e the algorithm to run in O(n log n) time. Second, given one perfect matchi ng, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented usin g depth-first search. A generalization of Kotzig's theorem proved by Jackso n and Whitty allows us to give a modification of the first algorithm that t ests whether a given graph has a unique f-factor, and find it if it exists. We also show how to modify the second algorithm to check whether a given f -factor is unique. Both extensions have the same time bounds as their perfe ct matching counterparts. For the weighted case, we can test in linear time whether a maximum-weight matching is unique, given the output from Edmonds ' algorithm for computing such a matching. The method is an extension of ou r algorithm for the unweighted case. (C) 2001 Academic Press .