A parallel MSF algorithm for planar graphs on a mesh and applications to image processing

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 nn 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.

Original languageEnglish (US)
Title of host publicationProceedings of 7th International Parallel Processing Symposium, IPPS 1993
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages205-211
Number of pages7
ISBN (Electronic)0818634421, 9780818634420
DOIs
StatePublished - 1993
Event7th International Parallel Processing Symposium, IPPS 1993 - Newport, United States
Duration: Apr 13 1993Apr 16 1993

Publication series

NameProceedings of 7th International Parallel Processing Symposium, IPPS 1993

Conference

Conference7th International Parallel Processing Symposium, IPPS 1993
CountryUnited States
CityNewport
Period4/13/934/16/93

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Hardware and Architecture
  • Software
  • Computational Theory and Mathematics
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'A parallel MSF algorithm for planar graphs on a mesh and applications to image processing'. Together they form a unique fingerprint.

Cite this