The Weighted Matching Approach to Maximum Cardinality Matching

Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday

Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa

Article type: Research Article

Authors: Gabow, Harold N.^{; *}

Affiliations: Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309-0430, USA. [email protected]

Correspondence: [*] Address for correspondence: Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309-0430, USA

Abstract: Several papers have achieved time Onm for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time Onm.

DOI: 10.3233/FI-2017-1555

Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 109-130, 2017