hal-00739360, version 3
Investigations on push-relabel based algorithms for the maximum transversal problem
Kamer Kaya
1Johannes Langguth 2Fredrik Manne 3Bora Uçar a, 2, 4
N° RR-8093 (2012)
Résumé : 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.
- a – CNRS
- 1 : Department of Biomedical Informatics
- The Ohio State University
- 2 : Laboratoire de l'Informatique du Parallélisme (LIP)
- Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
- 3 : Department of Informatics
- University of Bergen
- 4 : ROMA (ENS Lyon / CNRS / Inria Grenoble Rhône-Alpes)
- INRIA – École Normale Supérieure - Lyon – Laboratoire d'informatique du Parallélisme – CNRS : UMR5668
- Domaine : Informatique/Algorithme et structure de données
Informatique/Logiciel mathématiqueInformatique/Recherche opérationnelleInformatique/Mathématique discrèteMathématiques/Combinatoire - Référence interne : RR-8093
- Versions disponibles : v1 (08-10-2012) v2 (17-10-2012) v3 (31-10-2012)
- hal-00739360, version 3
- http://hal.inria.fr/hal-00739360
- oai:hal.inria.fr:hal-00739360
- Contributeur : Bora Uçar
- Soumis le : Mercredi 31 Octobre 2012, 12:59:01
- Dernière modification le : Mercredi 31 Octobre 2012, 15:37:57
Documents associés
Exporter