A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem

R.H. Bisseling; F. Manne

doi:10.1007/978-3-540-68111-3_74

A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem

R.H. Bisseling, F. Manne

Dep Wiskunde

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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 language	English
Title of host publication	Proceedings Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007
Editors	Roman Wyrzykowski
Publisher	Springer
Pages	708-717
Number of pages	10
ISBN (Print)	978-3-540-68105-2
DOIs	https://doi.org/10.1007/978-3-540-68111-3_74
Publication status	Published - 2008

Publication series

Name	Lecture Notes in Computer Science
Volume	4967

Keywords

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

Access to Document

10.1007/978-3-540-68111-3_74

ParallelFinal published version, 416 KB

Cite this

@inproceedings{9cb5bd040ad54d65a27697fd36276a3b,

title = "A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem",

abstract = "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.{"},",

keywords = "Wiskunde en Informatica (WIIN), Mathematics, Wiskunde en computerwetenschappen, Landbouwwetenschappen, Wiskunde: algemeen",

author = "R.H. Bisseling and F. Manne",

year = "2008",

doi = "10.1007/978-3-540-68111-3_74",

language = "English",

isbn = "978-3-540-68105-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "708--717",

editor = "Roman Wyrzykowski",

booktitle = "Proceedings Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007",

address = "Germany",

}

A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem. / Bisseling, R.H.; Manne, F.
Proceedings Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007. ed. / Roman Wyrzykowski. Springer, 2008. p. 708-717 (Lecture Notes in Computer Science; Vol. 4967).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem

AU - Bisseling, R.H.

AU - Manne, F.

PY - 2008

Y1 - 2008

N2 - 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.",

AB - 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.",

KW - Wiskunde en Informatica (WIIN)

KW - Mathematics

KW - Wiskunde en computerwetenschappen

KW - Landbouwwetenschappen

KW - Wiskunde: algemeen

U2 - 10.1007/978-3-540-68111-3_74

DO - 10.1007/978-3-540-68111-3_74

M3 - Conference contribution

SN - 978-3-540-68105-2

T3 - Lecture Notes in Computer Science

SP - 708

EP - 717

BT - Proceedings Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007

A2 - Wyrzykowski, Roman

PB - Springer

ER -

A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this