A parallel approximation algorithm for the weighted maximum matching problem

被引:0
|
作者
Manne, Fredrik [1 ]
Bisseling, Rob H. [2 ]
机构
[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway
[2] Univ Utrecht, Dept Math, NL-3508 TC Utrecht, Netherlands
来源
PARALLEL PROCESSING AND APPLIED MATHEMATICS | 2008年 / 4967卷
关键词
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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 [8] 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.
引用
收藏
页码:708 / +
页数:2
相关论文
共 50 条
  • [41] A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching
    Angriman E.
    Boroń M.
    Meyerhenke H.
    ACM Journal of Experimental Algorithmics, 2022, 27 (01):
  • [42] Maximum random fuzzy weighted matching models and hybrid genetic algorithm
    Gao, Xiaofeng
    Liu, Linzhong
    Proceedings of the Fourth International Conference on Information and Management Sciences, 2005, 4 : 466 - 472
  • [43] A linear algorithm to find the maximum-weighted matching in halin graphs
    Lu, Yunting
    Li, Yueping
    Lou, Dingjun
    IMECS 2007: INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS, VOLS I AND II, 2007, : 2274 - +
  • [44] A 2/3-approximation algorithm for vertex-weighted matching
    Al-Herz, Ahmed
    Pothen, Alex
    Discrete Applied Mathematics, 2022, 308 : 46 - 67
  • [45] A 2/3-approximation algorithm for vertex-weighted matching
    Al-Herz, Ahmed
    Pothen, Alex
    DISCRETE APPLIED MATHEMATICS, 2022, 308 : 46 - 67
  • [46] The Weighted Matching Approach to Maximum Cardinality Matching
    Gabow, Harold N.
    FUNDAMENTA INFORMATICAE, 2017, 154 (1-4) : 109 - 130
  • [47] APPROXIMATION ALGORITHMS FOR WEIGHTED MATCHING
    VENKATESAN, SM
    THEORETICAL COMPUTER SCIENCE, 1987, 54 (01) : 129 - 137
  • [48] A randomized algorithm for the on-line weighted bipartite matching problem
    Csaba, Bela
    Pluhar, Andras
    JOURNAL OF SCHEDULING, 2008, 11 (06) : 449 - 455
  • [49] An evolutionary algorithm for the robust maximum weighted independent set problem
    Klobucar, Ana
    Manger, Robert
    AUTOMATIKA, 2020, 61 (04) : 523 - 536
  • [50] A randomized algorithm for the on-line weighted bipartite matching problem
    Béla Csaba
    András Pluhár
    Journal of Scheduling, 2008, 11 : 449 - 455