FINDING CENTERS AND MEDIANS OF GRAPHS IN PARALLEL
作者:
PRANAY CHAUDHURI,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1996)
卷期:
Volume 9,
issue 1-2
页码: 111-118
ISSN:1063-7192
年代: 1996
DOI:10.1080/10637199608915567
出版商: Taylor & Francis Group
关键词: Parallel algorithm;graph;center;median;CREW PRAM;CRCW PRAM;time complexity;F.2.2;G.1.0
数据来源: Taylor
摘要:
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 ofnnodes, the proposed parallel algorithm can be implemented inO(log2n) time withO(n2n/logn) processors when no write-conflict is allowed by the computational model. On the other hand, the algorithm can be implemented inO(log n(loglogn)) time withO(n2n/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.
点击下载:
PDF (147KB)
返 回