Title :
On the parallel recognition of some tree-representable graphs
Author :
Lin, R. ; Olariu, S.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Geneseo, NY, USA
Abstract :
The authors present a fast parallel recognition algorithm for a class of tree-representable graphs and show how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation. With a graph G=(V,E) with |V|=n and |E|=m as input, the algorithms run in O(log n) time using O((n2 +mn)/log n) processors in the EREW-PRAM model
Keywords :
computational complexity; graph theory; parallel algorithms; trees (mathematics); EREW-PRAM model; data structures; parallel recognition algorithm; tree-representable graphs; Character recognition; Clustering algorithms; Terminology; Tree graphs;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143498
