Thumbnail
Access Restriction
Subscribed

Author Mller-Hannemann, Matthias ♦ Schwartz, Alexander
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword B-matching ♦ Blossom algorithm ♦ Operation counting
Abstract We present an experimental study of an implementation of weighted perfect $\textit{b}-matching$ based on the primal-dual blossom algorithm. Although this problem is well-understood in theory and efficient algorithms are known, only little experience with implementations is available. In this paper several algorithmic variants are compared on synthetic and application problem data of very sparse graphs. This study was motivated by the practical need for an efficient $\textit{b}-matching$ solver for the latter application, namely as a subroutine in our approach to a mesh refinement problem in computer-aided design (CAD).Linear regression and operation counting is used to analyze code variants. The experiments confirm that a fractional jump-start speeds up the algorithm, they indicate that a variant based on pairing heaps is slightly superior to a $\textit{k}-heap$ variant, and that scaling of large $\textit{b}-values$ is not necessary, whereas a delayed blossom shrinking heuristic significantly improves running times only for graphs with average degree two. The fastest variant of our implementation appears to be highly superior to a code by Miller and Pekny (1995).
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2000-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 5


Open content in new tab

   Open content in new tab
Source: ACM Digital Library