ALGORITHMS FOR FINDING AND UPDATING MINIMUM-DEPTH SPANNING-TREES IN PARALLEL

Fast parallel algorithms are presented for finding and updating the mi nimum-depth spanning trees of graphs. The computational model used is a parallel random access machine that allows simultaneous access to th e same memory location during both read and write operations. The para llel minimum-depth spanning tree algorithm is based on a partial spann ing tree doubling technique which is also found to be useful in updati ng the minimum-depth spanning tree when a new node or edge is added to the graph. The parallel minimum-depth spanning tree algorithm runs in O(log n log log n) time with O(n(2)[n/loglog n]) processors. The most notable results are O(loglog n) time parallel algorithms for updating the minimum-depth spanning tree solution when a new node (edge) is ad ded to an n node graph whose minimum-depth spanning tree is known.