Title :
A parallel MSF algorithm for planar graphs on a mesh and applications to image processing
Author_Institution :
Dept. of Comput. & Inf. Sci., New Jersey Inst. of Technol., Newark, NJ, USA
Abstract :
The author presents an efficient O(n) parallel algorithm for finding a minimum-cost spanning forest (MSF) of a weighted undirected planar graph with n2 edges, on an n ×n mesh-connected computer. He also obtains efficient MSF-based O(n) algorithms for several application problems in image processing. In particular, he shows that an MSF can be used to obtain more efficient and elegant O(n ) algorithms for the `k-width connectivity´ problem and the `optical clustering´ problem
Keywords :
image processing; parallel algorithms; image processing; k-width connectivity; mesh; mesh-connected computer; minimum-cost spanning forest; optical clustering; parallel MSF algorithm; planar graphs; Application software; Clustering algorithms; Computational geometry; Concurrent computing; Image processing; Labeling; Parallel algorithms; Terminology;
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
DOI :
10.1109/IPPS.1993.262882
