| Augment or Push? A computational study of Bipartite Matching and Unit Capacity Flow Algorithms (1997) | |||||||||||||||
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. 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. 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. 1. Introduction Maximum unit capacity flow and bipartite matching are two closely related combinatorial problems that have been extensively studied from the point of view of theoretical analysis of algorithms. See e.g. [19], [20, 21], [11], [3], [12]. The best bound for the former p... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||