Performance Studies of the Blossom V Algorithm
Links to Fileshttps://userpages.umbc.edu/~gobbert/papers/REU2015Team6.pdf
MetadataShow full item record
Type of Work24 pages
RightsThis item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
High Performance Computing Facility (HPCF)
The Blossom V algorithm is used in graph theory to compute a perfect matching of minimum cost. We conducted performance studies on the algorithm using the maya cluster in the UMBC High Performance Computing Facility to better understand the performance capabilities and emphasize potential approaches for improvement. In the performance studies, we varied the number of nodes, graph density, and weight range for numerous graphs. For each graph, we recorded execution times and memory usage. For all graphs used in the performance studies, we found that the majority of time is spent in initialization. We also found that as graph density increases, both execution time and memory usage increase. While we anticipated these conclusions, we reached other conclusions that were more surprising. We determined that as the weight range of a graph increases, initialization time and total execution time increase. We also found that scaling down integer weight ranges to real-valued weight ranges has a limited effect on initialization time and total execution time. Future studies should focus on speeding up the initialization process of the algorithm.