Performance Studies of the Blossom V Algorithm
Loading...
Links to Files
Permanent Link
Author/Creator ORCID
Date
2015
Type of Work
Department
Program
Citation of Original Publication
Rights
This 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.
Abstract
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.