Access Restriction

Author Mller-Hannemann, M. ♦ Schwartz, A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Algorithms ♦ B-matching ♦ Blossom algorithm ♦ Design patterns ♦ Experimentation ♦ Object-oriented design ♦ Software design
Abstract We present a case study on the design of an implementation of a fundamental combinatorial optimization problem: weighted $\textit{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 $\textit{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.
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 1999-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 4

Open content in new tab

   Open content in new tab
Source: ACM Digital Library