PARALLEL APPROXIMATE MATCHING
作者:
THOMASH. SPENCER,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1994)
卷期:
Volume 2,
issue 1-2
页码: 115-121
ISSN:1063-7192
年代: 1994
DOI:10.1080/10637199408915410
出版商: Taylor & Francis Group
关键词: Parallel computation;NC;approximate algorithm;matching;bipartite graph;deterministic;efficient;G.2.2;C.1.2;F.2.2
数据来源: Taylor
摘要:
Determining the parallel complexity of maximum cardinality matching in bipartite graphs is one of the most famous open problems in parallel algorithm design. The problem is known to be in RNC, but all known fast (polylogarithmic running time) parallel algorithms that find maximum cardinality matchings require the use of random numbers. Moreover, they are based on matrix algebra, so they are inherently inefficient for sparse graphs. Therefore, we are interested in the problem of finding an approximate maximum cardinality matching. The parallel matching algorithm of Goldberg, Plotkin and Vaidya (FOCS 1988) can be modified so that it runs in O(a2log3n) time on an EREW PRAM with n + m processors and finds a matching of size (1 - 1/a)p when given a graph with n vertices, m edges, and a maximum cardinality matching of size p. The resulting algorithm is deterministic.
点击下载:
PDF (150KB)
返 回