Parallel dynamic st-numbering and applications

Abstract

Given an arbitrary st-numbering of a biconnected graph of n vertices and m edges, parallel algorithms for dynamically finding another st-numbering of any specified pair of vertices on EREW P-RAM are presented. The algorithms run in O(log n) time using m/logn processors on EREW P-RAM. The dynamic st-numbering is applied to some network problems such as bipartition, centroid trees and centered trees construction.