Skip to Main content Skip to Navigation
Reports

Investigations on 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 augmenting path-based algorithms and the recently proposed pseudoflow approach. 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

https://hal.inria.fr/hal-00739360
Contributor : Bora Uçar <>
Submitted on : Wednesday, October 17, 2012 - 2:19:58 PM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM
Long-term archiving on: : Saturday, December 17, 2016 - 2:04:01 AM

File

rr-8093.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00739360, version 2

Collections

Citation

Kamer Kaya, Johannes Langguth, Fredrik Manne, Bora Uçar. Investigations on push-relabel based algorithms for the maximum transversal problem. [Research Report] RR-8093, 2012, pp.27. ⟨hal-00739360v2⟩

Share

Metrics

Record views

43

Files downloads

26