Efficient Parallel and External Matching

被引：0

作者：

Birn, Marcel ^{[1
]}

Osipov, Vitaly ^{[1
]}

Sanders, Peter ^{[1
]}

Schulz, Christian ^{[1
]}

Sitchinava, Nodari ^{[1
]}

机构：

[1] Karlsruhe Inst Technol, D-76021 Karlsruhe, Germany

来源：

EURO-PAR 2013 PARALLEL PROCESSING | 2013年 / 8097卷

关键词：

ALGORITHM; COMPLEXITY;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study a simple parallel algorithm for computing matchings in a graph. A variant for unweighted graphs finds a maximal matching using linear expected work and O(log(2) n) expected running time in the CREW PRAM model. Similar results also apply to External Memory, MapReduce and distributed memory models. In the maximum weight case the algorithm guarantees a 1/2-approximation. Although the parallel execution time is linear for worst case weights, an experimental evaluation indicates good scalabilty on distributed memory machines and on GPUs. Furthermore, the solution quality is very good in practice.

引用

页码：659 / 670

页数：12

共 24 条

[1] THE INPUT OUTPUT COMPLEXITY OF SORTING AND RELATED PROBLEMS
AGGARWAL, A
VITTER, JS
[J]. COMMUNICATIONS OF THE ACM, 1988, 31 (09) : 1116 - 1127
[2] [Anonymous], P 16 INT C STRUCT IN
[3] Auer Bas O. Fagginger, 2012, Facing the Multicore-Challenge II. Aspects of New Paradigms and Technologies in Parallel Computing, P108, DOI 10.1007/978-3-642-30397-5_10
[4] Birn M., 2013, CORR
[5] Birn M., 2012, THESIS KARLSRUHE I T
[6] Blelloch Guy E., 2012, P 24 ACM S PAR ALG A, P308, DOI DOI 10.1145/2312005.2312058
[7] Drake DE, 2003, LECT NOTES COMPUT SC, V2764, P14
[8] Frigo M., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P285, DOI 10.1109/SFFCS.1999.814600
[9] Goodrich MT, 2011, LECT NOTES COMPUT SC, V7074, P374, DOI 10.1007/978-3-642-25591-5_39
[10] Hoepman J.-H., 2004, CoRR

← 1 2 3 →