AN O(LOG N) ALGORITHM FOR PARALLEL UPDATE OF MINIMUM SPANNING-TREES

作     者：PAWAGI, S RAMAKRISHNAN, IV 

作者机构：Department of Computer Science University of Maryland College Park MD 20742 U.S.A. 

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

年 卷 期：1986年第22卷第5期

页      面：223-229页

核心收录：

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

基　　金：National Science Founda-tion, (ECS-84-04399) Office of Naval Research, ONR, (N00014-84-K-0530) Air Force Office of Scientific Research, AFOSR, (F49620-85-K-0009) 

主　　题：Spanning tree graph algorithm 

摘      要：Incremental graph algorithms deal with recomputing properties of a graph after an incremental change is made to that graph, such as adding and deleting vertices and edges. Such recomputations are updating graph properties. Efficient parallel algorithms are presented for edge and vertex insertion updating in a minimum spanning tree (MST) due to changes in edge costs or in vertex insertion, when a new node is inserted in the underlying graph. The algorithms are derived from a computational model of an unbounded parallel random access machine where simultaneous reads, but not simultaneous writes, are allowed into the same memory location. They are shown to be more efficient than previously proposed algorithms for the MST updating problem, requiring only O(log n) time and certain processors. Main features of the algorithms are that they: 1. solve MST updating problems based on the use of an inverted tree, and 2. exploit a certain MST property that allows novel solution for vertex updating.