An optimal EREW PRAM algorithm for minimum spanning tree verification

作     者：King, V Poon, CK Ramachandran, V Sinha, S 

作者机构：UNIV TEXASDEPT COMP SCIAUSTINTX 78712 UNIV VICTORIADEPT COMP SCIVICTORIABCCANADA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1997年第62卷第3期

页      面：153-159页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Texas Advanced Research Projects, (0003658386) National Science Foundation, NSF, (CCR/GER 90-23059) National Science Foundation, NSF Natural Sciences and Engineering Research Council of Canada, NSERC 

主　　题：parallel algorithms minimum spanning tree verification EREW PRAM design of algorithms optimal algorithm 

摘      要：We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(log n) time and O(m + n) work. The algorithm is a parallelization of King s Linear time sequential algorithm for the problem. (C) 1997 Elsevier Science B.V.