ePubs
The open archive for STFC research publications
Home
About ePubs
Content Policies
News
Help
Privacy/Cookies
Suggest an Enhancement
Contact ePubs
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
Contributors
IS Duff (STFC Rutherford Appleton Lab.)
,
K Kaya (CERFACS)
,
B Ucar (Lyon U.)
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
Showing record 1 of 1
Recent Additions
Browse Organisations
Browse Journals/Series
Login to add & manage publications and access information for OA publishing
Username:
Password:
Useful Links
Chadwick & RAL Libraries
SHERPA FACT
SHERPA RoMEO
SHERPA JULIET
Journal Checker Tool
Google Scholar