 | The ACM Journal of Experimental Algorithmics |
Volume 4, Article 7, 1999
Implementing Weighted b-matching Algorithms: Towards a Flexible
Software Design
by
and
http://www.jea.acm.org/1999/MuellerMatching/
Abstract:
We present a case study on the design of an implementation of a
fundamental combinatorial optimization problem: weighted b-matching.
Although this problem is well-understood in theory and efficient
algorithms are known, only little experience with
implementations is available.
This study was motivated by the practical need for an
efficient b-matching solver as a subroutine in our approach to
a mesh refinement problem in computer-aided design (CAD).
The intent of this paper is to demonstrate the importance of flexibility and
adaptability in the design of complex algorithms, but also to
discuss how such goals can be achieved for matching algorithms
by the use of design patterns.
Starting from the basis of the famous blossom algorithm we
explain how to exploit in different ways the flexibility of
our software design which allows an incremental improvement of
efficiency by exchanging subalgorithms and data structures.
In a comparison with a code by Miller and Pekny
we also demonstrate that our implementation is even without fine-tuning
very competitive. Our code is significantly faster, with improvement factors
ranging between 15 and 466 on TSPLIB instances.
- Keywords: b-matching, blossom algorithm,
object-oriented design, design patterns
- CR Categories:
G.2.2 Discrete Mathematics: Graph Theory [Graph Algorithms],
G.4 Mathematical Software: Algorithm Design and Analysis,
G.4 Mathematical Software: Efficiency
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the article;
this is a small Unix tar file, which includes the source code, a Makefile,
and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
April 1, 1999
|
February 3, 2000
|
February 23, 2000
|
May 10, 2000
|
Last updated and validated May 10, 2000, by editor@jea.acm.org