s'authentifier
version française rss feed

hal-00739360, version 3

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

Kamer Kaya () 1, Johannes Langguth 2, Fredrik Manne () 3, Bora Uçar () a24

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.

  • Domaine : Informatique/Algorithme et structure de données
    Informatique/Logiciel mathématique
    Informatique/Recherche opérationnelle
    Informatique/Mathématique discrète
    Mathé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
  • oai:hal.inria.fr:hal-00739360
  • Contributeur : 
  • Soumis le : Mercredi 31 Octobre 2012, 12:59:01
  • Dernière modification le : Mercredi 31 Octobre 2012, 15:37:57
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...