Unique Maximum Matching Algorithms

Harold N. Gabow, Haim Kaplan, Robert E. Tarjan

Research output: Contribution to journalArticle

29 Scopus citations

Abstract

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. First, 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. For the special case of planar graphs, we improve the algorithm to run in O(n log n) time. Second, 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. A generalization of Kotzig's theorem proved by Jackson and Whitty 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.

Original languageEnglish (US)
Pages (from-to)159-183
Number of pages25
JournalJournal of Algorithms
Volume40
Issue number2
DOIs
StatePublished - Aug 2001

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Keywords

  • Blossom shrinking
  • Depth first search
  • Dynamic graph 2-edge connectivity
  • Kotzig's theorem
  • Maximum matching
  • Unique maximum matching
  • Unique perfect matching

Fingerprint Dive into the research topics of 'Unique Maximum Matching Algorithms'. Together they form a unique fingerprint.

  • Cite this