Design, implementation, and analysis of maximum transversal algorithms

Abstract : We report on careful implementations of seven algorithms for solving the problem of finding a maximum transversal of a sparse matrix. We analyze the algorithms and discuss the design choices. To the best of our knowledge, this is the most comprehensive comparison of maximum transversal algorithms based on augmenting paths. Previous papers with the same objective either do not have all the algorithms discussed in this article or they used nonuniform implementations from different researchers. We use a common base to implement all of the algorithms and compare their relative performance on a wide range of graphs and matrices. We systematize, develop, and use several ideas for enhancing performance. One of these ideas improves the performance of one of the existing algorithms in most cases, sometimes significantly. So much so that we use this as the eighth algorithm in comparisons.
Type de document :
Article dans une revue
ACM Transactions on Mathematical Software, Association for Computing Machinery, 2011, 38, pp.13:1--13:31. 〈10.1145/2049673.2049677〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00786548
Contributeur : Equipe Roma <>
Soumis le : vendredi 8 février 2013 - 20:07:17
Dernière modification le : mardi 16 janvier 2018 - 15:50:59

Identifiants

Collections

Citation

Iain S. Duff, Kamer Kaya, Bora Uçar. Design, implementation, and analysis of maximum transversal algorithms. ACM Transactions on Mathematical Software, Association for Computing Machinery, 2011, 38, pp.13:1--13:31. 〈10.1145/2049673.2049677〉. 〈hal-00786548〉

Partager

Métriques

Consultations de la notice

129