Skip to Main content Skip to Navigation
Journal articles

Push-relabel based algorithms for the maximum transversal problem

Abstract : We investigate the push-relabel algorithm for solving the problem of finding a maximum cardinality matching in a bipartite graph in the context of the maximum transversal problem. We describe in detail an optimized yet easy-to-implement version of the algorithm and fine-tune its parameters. We also introduce new performance-enhancing techniques. On a wide range of real-world instances, we compare the push-relabel algorithm with state-of-the-art algorithms based on augmenting paths and pseudoflows. We conclude that a carefully tuned push-relabel algorithm is competitive with all known augmenting path-based algorithms, and superior to the pseudoflow-based ones.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Thursday, March 7, 2013 - 5:18:59 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Friday, March 31, 2017 - 6:46:16 PM


Files produced by the author(s)




Kamer Kaya, Johannes Langguth, Fredrik Manne, Bora Uçar. Push-relabel based algorithms for the maximum transversal problem. Computers and Operations Research, Elsevier, 2013, 40 (5), pp.1266-1275. ⟨10.1016/j.cor.2012.12.009⟩. ⟨hal-00763920⟩



Record views


Files downloads