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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00763920
Contributor : Equipe Roma <>
Submitted on : Thursday, March 7, 2013 - 5:18:59 PM
Last modification on : Tuesday, June 30, 2020 - 3:34:02 PM
Long-term archiving on: : Friday, March 31, 2017 - 6:46:16 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

490

Files downloads

856