The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/54399
Record Status Checked
Record Id 54399
Title Design, implementation, and analysis of maximal 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 analyse 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 paper or they used non-uniform 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.
Organisation CSE , CSE-NAG , STFC
Keywords assignment , matrix transversals , Bipartite graphs , matching , breadth first search , graph theory , depth first search
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Preprints RAL-P-2010-001. 2010. RAL-P-2010-001.pdf 2010
Journal Article ACM Trans Math Software 38, no. 2 (2012): 13. doi:10.1145/2049673.2049677 2012