Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, February 15, 2022 - 10:55:25 PM
Last modification on : Friday, November 18, 2022 - 9:27:50 AM
Long-term archiving on: : Monday, May 16, 2022 - 9:01:36 PM


Files produced by the author(s)




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



Record views


Files downloads