Loading...
Please wait, while we are loading the content...
Unique maximum matching algorithms (2002).
| Content Provider | CiteSeerX |
|---|---|
| Author | Tarjan, Robert E. Gabow, Harold N. Kaplan, Haim |
| 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 log^4 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... |
| File Format | |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Subject Keyword | Recent Dynamic Connectivity Algorithm Unique Perfect Matchings Special Case Old Result Weighted Case Unweighted Case Unique Maximum Matching Algorithm Unique Perfect Matching Maximum Matchings |
| Content Type | Text |