FINDING CENTERS AND MEDIANS OF GRAPHS IN PARALLEL

Abstract

This paper presents a parallel algorithm for finding the centers and medians of graphs. The computational model used is a shared memory single instruction stream, multiple data stream computer which is more commonly known as the parallel random access machine. The design of the parallel algorithm is based on the growing-by-doubling paradigm. Assuming that the graph consists of n nodes, the proposed parallel algorithm can be implemented in O(log ² n) time with O(n ² n/logn) processors when no write-conflict is allowed by the computational model. On the other hand, the algorithm can be implemented in O(log n(loglogn)) time with O(n ² n/loglogn) processors when the computational model allows write-conflict. In case of write-conflict, it is assumed that all the processors involved in the concurrent-write operation must attempt to write the same value.

KEY WORDS:

• Parallel algorithm
• graph
• center
• median
• CREW PRAM
• CRCW PRAM
• time complexity

C.R. CATEGORIES:

• F.2.2
• G.1.0