Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
85232

Sep 10, 2001

A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs
Norbert Blum
[Download PostScript] [Download PDF]

In [2,3], we have reduced the problem of finding an augmenting path in a general graph to a reachability problem in a directed, bipartite graph, and we have shown that a slight modification of depth-first search leads to an algorithm for finding such paths. This new point of view enables us to give a simplified realization of the Hopcroft-Karp approach for the computation of a maximum cardinality matching in general graphs. We show, how to get an O(n+m) implementation of one phase leading to an O(n1/2m) algorithm for the computation of a maximum cardinality matching in general graphs.

Last Change: 08/16/04 at 12:32:20
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V