@inproceedings{f6d177cdddb7419db5450abd71afac9d,
title = "EFFICIENT CONNECTED COMPONENTS ALGORITHM ON A MESH-CONNECTED COMPUTER.",
abstract = "An algorithm for identifying the connected components of an undirected graph on a mesh-connected computer is presented. If the graph has n vertices and m edges, a q-dimensional mesh-connected computer having 2m processors is used and computes the connected components in O(q**2 (m**1 **/ **Q plus n**1 **/ **Q )log n)) time. This algorithm can be extended to compute a minimal spanning tree of an undirected graph within the same processor and time bounds. For sparse graphs the algorithm has better time performance and uses a significantly less number of processors than existing mesh-connected computer algorithms for this problem. For dense graphs the algorithm can be speeded up by using a higher dimensional mesh.",
author = "Gopalakrishnan, \{P. S.\} and Ramakrishnan, \{I. V.\} and Kanal, \{L. N.\}",
year = "1985",
language = "English",
isbn = "0818606371",
series = "Proceedings of the International Conference on Parallel Processing",
publisher = "IEEE",
pages = "711--714",
editor = "Douglas DeGroot",
booktitle = "Proceedings of the International Conference on Parallel Processing",
}