### Augment or push: a computational study of bipartite matching and unit-capacity flow algorithmsAugment or push: a computational study of bipartite matching and unit-capacity flow algorithms

Access Restriction
Subscribed

 Author Cherkassky, Boris V. ♦ Goldberg, Andrew V. ♦ Martin, Paul ♦ Setubal, Joao C. ♦ Stolfi, Jorge Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1998 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Abstract We conduct a computational study of unit capacity flow and bipartite matching algorithms. Our goal is to determine which variant of the push-relabel method is most efficient in practice and to compare push-relabel algorithms with augmenting path algorithms. We have implemented and compared three push-relabel algorithms, three augmenting-path algorithms (one of which is new), and one augment-relabel algorithm. The depth-first search augmenting path algorithm was thought to be a good choice for the bipartite matching problem, but our study shows that it is not robust (meaning that it is not consistently fast on all or most inputs). For the problems we study, our implementations of the FIFO and lowest-level selection push-relabel algorithms have the most robust asymptotic rate of growth and work best overall. Augmenting path algorithms, although not as robust, on some problem classes are faster by a moderate constant factor. Our study includes several new problem families and input graphs with as many as 5 × $10^{5}$ vertices. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1998-09-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 3

#### Open content in new tab

Source: ACM Digital Library