TY - JOUR

T1 - Unique maximum matching algorithms

AU - Gabow, Harold N.

AU - Kaplan, Haim

AU - Tarjan, Robert E.

N1 - Funding Information:
1A preliminary version of part of our work was presented at the 31st Annual ACM Symposium on Theory of Computing 11 . 2 Research at Princeton University partially supported by NSF Grant CCR-9626862.

PY - 1999

Y1 - 1999

N2 - We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. Given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log4 n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. Also, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. We prove a generalization of Kotzig's theorem characterizing unique f-factors in terms of bridges. This theorem allows us to give a modification of the first algorithm that tests 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 perfect 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 our algorithm for the unweighted case.

AB - We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. Given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log4 n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. Also, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. We prove a generalization of Kotzig's theorem characterizing unique f-factors in terms of bridges. This theorem allows us to give a modification of the first algorithm that tests 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 perfect 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 our algorithm for the unweighted case.

UR - http://www.scopus.com/inward/record.url?scp=0032650473&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032650473&partnerID=8YFLogxK

U2 - 10.1145/301250.301273

DO - 10.1145/301250.301273

M3 - Conference article

AN - SCOPUS:0032650473

SP - 70

EP - 78

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0734-9025

T2 - Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99

Y2 - 1 May 1999 through 4 May 1999

ER -