Algorithms for finding centers and medians of trees and graphs on a parallel computation modeI

Abstract

This paper presents synchronized parallel algorithms for finding centres and medians of trees and graphs. The computation model used is a shared memory single instruction stream, multiple data stream computer that allows both read and write conflicts. Assuming that all the trees and graphs under investigation consists of n nodes, the time bound achieved by the algorithm for trees os 0(log n) with n2 processors whereas the same for graphs is 0(logd.log log n) with n2[n/log logn] processors, where d is the graph diameter.