Investigations on push-relabel based algorithms for the maximum transversal problem

Résumé : Nous étudions le problème de couplage maximum dans des graphes bipartis. Nous décrivons en détail une version optimisée de l'algorithme en ajustant ses paramètres. L'algorithme est facile à mettre en œuvre. Nous introduisons également de nouvelles techniques pour améliorer la performance de l'algorithme. Sur un large éventail de cas du monde réel, nous comparons l'algorithme Push-Relabel avec des algorithmes basés sur les concepts de chemins augmentants et de pseudoflot récemment proposés. Nous concluons qu'un algorithme de type Push-Relabel soigneusement réglé est en concurrence avec tous les algorithmes connus de type chemins augmentants, et supérieur à ceux de type pseudoflot.


https://hal.inria.fr/hal-00739360
Contributeur : Bora Uçar <>
Soumis le : mercredi 31 octobre 2012 - 12:59:01
Dernière modification le : samedi 17 septembre 2016 - 01:36:56

Fichier

rr-8093.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00739360, version 3

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, INRIA. 2012, pp.27. <hal-00739360v3>

Exporter

Partager

Métriques

Consultations de
la notice

185

Téléchargements du document

208