OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS
作者:
HIRYOUNG KIM,
ALANP. SPRAGUE,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1997)
卷期:
Volume 10,
issue 3-4
页码: 165-176
ISSN:1063-7192
年代: 1997
DOI:10.1080/10637199708915615
出版商: Taylor & Francis Group
关键词: bipartite permutation graphs;complexity;maximum matching;Parallel algorithms;parallel prefix
数据来源: Taylor
摘要:
We present a cost-optimal parallel algorithm for the maximum matching problem on bipartite permutation graphs on an EREW PRAM. Previously, Chen and Yesha have dealt with this problem. Their solution relies on Dekel and Sahni's matching algorithm for convex bipartite graphs, which runs in O(log2n) time usingO(n) processors. Given a permutation diagram, our algorithm runs in O(logn) time by using O(n/logn) processors. Our method starts with an easily understood greedy algorithm. We define a nontrivial binary operation which is associative and equivalent to the greedy algorithm. Thus parallel prefix can be applied to the problem.
点击下载:
PDF (199KB)
返 回