direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 591-1998

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Implementing Weighted b-Matching Algorithms: Towards a Flexible Software Design
journal version appeared in the ACM Journal of Experimental Algorithmics, volume 4, Article 7, 1999; extended abstract appeared in Proceedings of the 2nd Workshop on Algorithm Engineering (WAE'98), Kurt Mehlhorn (Ed.), pages 86-97, Max-Planck-Institut für Informatik, Saarbrücken
CR: G.2.2 Discrete Mathematics: Graph Theory [Graph Algorithms], G.4 Mathematical Software: Algorithm Design and Analysis, G.4 Mathematical Software: Efficiency
b-matching, blossom algorithm, object-oriented design, design patterns
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 Pulleyblank's 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.
Download as [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe