Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning treeFootnote^∗

^∗Work partially supported by an Australian Research Council Grant and done during the author's visit at Abo Akademi University

References

• Brent , R.P. 1974 . The parallel evaluation of general arithmetic expression . J. of ACM , 21 : 201 – 206 .
   Web of Science ®Google Scholar
• Chong K. W. Lam T. W. Finding Minimum Spanning Trees on the EREW PRAM 1996
   Google Scholar
• Cole , R. and Vishkin , U. . Approximate and exact parallel scheduling with applications to list, tree and graph problems . 27th IEEE Symposium on Foundations of Computer Science . pp. 478 – 491 .
   Google Scholar
• Cole , R. and Vishkin , U. 1988 . Approximate parallel scheduling, Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time . SIAM J. Comput , 17 : 128 – 142 .
   Web of Science ®Google Scholar
• Dixon , B. and Tarjan , R.E. . Optimal parallel verification of minimum spanning trees in logarithmic time . Canada-France Conference on Parallel and Distributed Computing, Theory and Practice .
   Google Scholar
• Hsu , L.H. , Jan , R.H. , Lee , Y.C. , Hung , C.N. and Chern , M.S. 1991 . Finding the most vital edge with respect to minimum spanning tree in weighted graphs . Information Processing Letters , 39 : 277 – 281 .
   Web of Science ®Google Scholar
• Hsu , L.H. , Wang , P.F. and Wu , C.T. 1992 . Parallel algorithms for finding the most vital edge with respect to minimum spanning tree . Parallel Computing , 18 : 1143 – 1155 .
   Web of Science ®Google Scholar
• Iwano , K. and Katoh , N. 1993 . Efficient algorithms for finding the most vital edge of a minimum spanning tree . Information Processing Letters , 48 : 211 – 213 .
   Web of Science ®Google Scholar
• Jaja , J. 1992 . An Introduction to Parallel Algorithms , Addison-Wesley .
   Google Scholar
• Katajainen , J. and Träff , J.L. 1994 . Simple parallel algorithms for the replacement edge problem and related problems on minimum spanning trees,Department of Computer Science , University of Copenhagen . Technical Report DIKU-94/18
   Google Scholar
• Schieber , B. and Vishkin , U. 1988 . On finding lowest common ancestors: Simplification and parallelization . SIAM J. Comput , 17 : 1253 – 1262 .
   Web of Science ®Google Scholar
• Suraweera , F. and Maheshwari , P. . A parallel algorithm for the most vital edge problem on the CRCW-SIMD computational model . Proc. 17th Annual Computer Science Conf . Christchurch.
   Google Scholar
• Suraweera , F. , Maheshwari , P. and Bhattacharya , P. 1995 . Optimal algorithms to find the most vital edge of a minimum spanning tree , Griffith University . Technical Report CIT-95-21, School of Computing and Information Technology
   Google Scholar
• Tarjan , R.E. 1979 . Applications of path compression on balanced trees . Journal of ACM , 26 : 690 – 715 .
   Web of Science ®Google Scholar
• Tarjan , R.E. 1982 . Sensitivity analysis of minimum spanning trees and shortest path trees . Information Processing Letters , 14
   Web of Science ®Google Scholar