OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS

References

• Alt , H. , Blum , N. , Mehlhorn , K. and Paul , M. , ( 1991 ). Computing a maximum cardinality matching in a bipartite graph in lime O(n1.5 √m/ log n) . Inform. Proc. Lett. , 31 , 237 – 240 .
   Google Scholar
• Akl , S. G. , ( 1989 ) . The Design and Analysis of Parallel Algorithms . Prentice Hall , ch. 2 , 49 .
   Google Scholar
• Chen , L. , and Yesha , Y. , ( 1993 ). Efficient parallel algorithms for bipartite permutation graphs , Networks , 22 , 29 – 39 .
   Google Scholar
• Dekel , E. and Sahni , S. , ( 1984 ), A parallel matching algorithm for convex bipartite graphs and applications to scheduling , J. of Parallel and Distr. Computing , 1 , 185 – 205 .
   Web of Science ®Google Scholar
• Even , S. , Itahi , A. and Shamir , A. , ( 1976 ), On the complexity of timetable and multicommodity flow problems , SIAM Jo. Comput. , 5 , 691 – 703 .
   Google Scholar
• Hagerup , T. and Rub , C. , ( 1989 ). Optimal merging and sorting on the EREW PRAM , Inform. Proc. Lett . 33 , 181 – 185 .
   Google Scholar
• Jaja , J. , ( 1992 ) . An Introduction to Parallel Algorithms. ( Addison-Wcsley ) , ch. 2 , 44 .
   Google Scholar
• Micali , S. and Vazirani , V. V. , ( 1980 ) . An O(√|V||E|) algorithm for finding maximum matching on general graphs . Proc. of 21st Ann. Symp. Found. Of Comp. Sci. , 17 – 25 .
   Google Scholar
• Moitra , A. and Johnson , R. , ( 1989 ) . Parallel algorithms for maximum matching and other problems on interval graphs . Technical Report Cornell Univ .
   Google Scholar
• Rhee , C. and Liang , Y. D. , (1994) . Finding a maximum matching in a permutation graph . Proc. Of 32nd Ann. Southeast Conf. , 69 – 73 .
   Google Scholar
• Spinard , J. , Brandstaedt , A. and Stewart , L. , ( 1987 ). Bipartite permutation graphs . DAM , 18 , 279 – 292 .
   Google Scholar