Can I read Unique Maximum Matching Algorithms on EtoBox?

Unique Maximum Matching Algorithms by Harold N Gabow; Haim Kaplan; Robert E Tarjan is a Computer Science article available to read on EtoBox.

What is Unique Maximum Matching Algorithms about?

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 Ž 4 . graph has a unique perfect matching, and find it if it exists, in O m log 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. 1 A preliminary version of part of our work was presented at the 31st Annual ACM w x Symposium on Theory of Computing 11 .

Who reads Unique Maximum Matching Algorithms?

Author

Harold N Gabow; Haim Kaplan; Robert E Tarjan

Publisher

Elsevier Science; Elsevier ; Academic Press; Elsevier BV (ISSN 0196-6774)

Published

2001

Language

EN

Field

Computer Science (Physical Sciences)