Implementing weighted b-matching algorithms
Open Access
- 31 December 2000
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 5
Abstract
We present an experimental study of an implementation of weighted perfect 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 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 k-heap variant, and that scaling of large 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).Keywords
This publication has 20 references indexed in Scilit:
- Implementing weighted b-matching algorithmsACM Journal of Experimental Algorithmics, 1999
- On the efficiency of pairing heaps and related data structuresJournal of the ACM, 1999
- Mesh refinement via bidirected flowsJournal of the ACM, 1997
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Pairing heapsCommunications of the ACM, 1987
- A polynomial algorithm for b-matchings: An alternative approachInformation Processing Letters, 1987
- The pairing heap: A new form of self-adjusting heapAlgorithmica, 1986
- An analysis of alternative strategies for implementing matching algorithmsNetworks, 1983
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965