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 metadatas

https://hal.inria.fr/hal-00786548
Contributor : Equipe Roma <>
Submitted on : Friday, February 8, 2013 - 8:07:17 PM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

203