A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH

References

• R. E. Tarjan , Data Structures and Network Algorithms , SIAM Publication , 1983 .
   Google Scholar
• G. Lev , Size bounds and parallel algorithms for networks , Tech. Report, CST-8-80 , Dept. of Computer Science, Univ. of Edinburgh , 1980 .
   Google Scholar
• R. M. Karp and W. Wigderson , A fast parallel algorithm for maximal independent set problem , Proc. 16th Ann. ACM Symp. on Theory of Computing ( 1984 ), 266 – 272 .
   Google Scholar
• A. Israeli and Y. Shiloach , An improved parallel algorithm for maximal matching , Information Processing Letter 22 ( 1986 ), 57 – 60 .
   Web of Science ®Google Scholar
• A. K. Datta and R. K. Sen , An efficient parallel algorithm for maximal matching , Lecture Notes in Computer Science 634 ( 1992 ), 813 .
   Google Scholar
• T. Hugerup , Planar depth-first search in O(logn) time , SIAM J. Computing , 19 , 4 ( 1990 ), 678 – 704 .
   Web of Science ®Google Scholar
• X. He , Efficient parallel algorithm for solving some tree problems , Proc. Twenty-Fourth Annu. Allerton periodicerence on Communication, Control and Computing , Monticello , IL , USA , Oct. 1–3 , 1986 , 777 – 787 .
   Google Scholar
• A. Moitra and R. Johnson , PT-optimal algorithm for interval graphs , Proc. 26th Annu. Allerton periodic. on Commun., Control and Computing , 1 , Monticello , IL , 1988 , 274 – 282 .
   Google Scholar
• M. Luby , A simple parallel algorithm for maximal independent set , SIAM J. Comput . 15 ( 1986 ), 1036 – 1053 .
   Web of Science ®Google Scholar
• M. Luby , Removing randomness in parallel coputation without a processor penalty , private communication. .
   Google Scholar
• A. V. Goldberg , S. A. Plotkin and G. E. Shannon , Parallel symmetry-breaking in sparse graphs , SIAM J. Discrete Math . 1 ( 1988 ), 434 – 446 .
   Google Scholar