DocumentCode :
2183253
Title :
Solving some graph problems with optimal or near-optimal speedup on mesh-of-trees networks
Author :
Huang, Ming-Deh A.
fYear :
1985
fDate :
21-23 Oct. 1985
Firstpage :
232
Lastpage :
240
Abstract :
We present a systematic approach for solving graph problems under the network models. We illustrate this approach on the mesh-of-trees networks. It is known that under the CREW PRAM model, when a undirected graph of n nodes is given by an n by n adjacency matrix, the problems of finding minimum spanning forest, connected components, and biconnected components can all be solved with optimal speedup when the number of processors p ≤ n2/log2n. We show that for these problems, the same optimal speedup can be achieved even under the much more restrictive mesh-of-trees network. We also show that for the problem of finding directed spanning forest of arbitrary digraphs and the problem of testing strong connectivity of 1-reachable digraphs, near-optimal speedup can be achieved.
Keywords :
Binary trees; Computational modeling; Computer networks; Computer science; Concurrent computing; Phase change random access memory; Read-write memory; TV; Testing; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1985., 26th Annual Symposium on
Conference_Location :
Portland, OR, USA
ISSN :
0272-5428
Print_ISBN :
0-8186-0644-4
Type :
conf
DOI :
10.1109/SFCS.1985.52
Filename :
4568146
Link To Document :
بازگشت