首页   按字顺浏览 期刊浏览 卷期浏览 PARALLEL APPROXIMATE MATCHING
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)



返 回