首页   按字顺浏览 期刊浏览 卷期浏览 IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH
IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH

 

作者: ALAKKUMAR DATTA,   RANJANKUMAR SEN,  

 

期刊: Parallel Algorithms and Applications  (Taylor Available online 2000)
卷期: Volume 14, issue 4  

页码: 321-327

 

ISSN:1063-7192

 

年代: 2000

 

DOI:10.1080/10637199808947393

 

出版商: Taylor & Francis Group

 

关键词: Parallel graph algorithms;Depth first search tree;Matching;Parallel graph algorithms;Depth first search tree;Matching

 

数据来源: Taylor

 

摘要:

Computation of maximal matching of a graph based on Depth First Search tree computation was introduced by Datta and Sen (Parallel Algorithms and Applications,5, 1995, 161-164). They showed that the approach gives efficient parallel algorithms for maximal matching for graphs for which DFS tree can be efficiently computed. They also presented a parallel scheme to compute a maximal matching in O(T(n) log n) time using O(P(n)) number of processors, where T(n) and P(n) are the time and the number of processors required to compute DFS tree of a graph in parallel. We present here, an improved technique to compute maximal matching in parallel based on DFS tree computation. The algorithm takes O(T(n)) time and O(P(n)) processors.

 

点击下载:  PDF (186KB)



返 回