A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem

R.H. Bisseling, F. Manne

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


We consider the problem of computing a weighted edge matching in a large graph using a parallel algorithm. This problem has application in several areas of combinatorial scientific computing. Since an exact algorithm for the weighted matching problem is both fairly expensive to compute and hard to parallelise we instead consider fast approximation algorithms. We analyse a distributed algorithm due to Hoepman and show how this can be turned into a parallel algorithm. Through experiments using both complete as well as sparse graphs we show that our new parallel algorithm scales well using up to 32 processors.",
Original languageEnglish
Title of host publicationProceedings Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007
EditorsRoman Wyrzykowski
Number of pages10
ISBN (Print)978-3-540-68105-2
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science


  • Wiskunde en Informatica (WIIN)
  • Mathematics
  • Wiskunde en computerwetenschappen
  • Landbouwwetenschappen
  • Wiskunde: algemeen


Dive into the research topics of 'A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem'. Together they form a unique fingerprint.

Cite this