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)
返 回