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.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2013, 40 (5), pp.1266-1275. 〈10.1016/j.cor.2012.12.009〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00763920
Contributeur : Equipe Roma <>
Soumis le : jeudi 7 mars 2013 - 17:18:59
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : vendredi 31 mars 2017 - 18:46:16

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

297