Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14578
For citation please use:
Main Title: Implementing Weighted b-Matching Algorithms: Towards a Flexible Software Design
Author(s): Müller-Hannemann, Matthias
Schwartz, Alexander
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15805
http://dx.doi.org/10.14279/depositonce-14578
License: http://rightsstatements.org/vocab/InC/1.0/
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 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.
Subject(s): b-matching
blossom algorithm
object-oriented design
design patterns
Issue Date: 1998
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1998, 591
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-591-1998.pdf
Format: Adobe PDF | Size: 24.04 MB
DownloadShow Preview
Thumbnail
Report-591-1998.ps
Format: Postscript | Size: 1.19 MB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.