Parallel optimal weighted links

Ovidiu Daescu, Yam K. Cheung, James D. Palmer

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


In this paper we consider parallel algorithms for computing an optimal link among weighted regions in the plane. The problem arises in several areas, including radiation therapy, geological exploration and environmental engineering. We present a CREW PRAM parallel algorithm and a coarse-grain parallel computer algorithm for this problem. For a weighted subdivision with n vertices, the work of the parallel algorithms we propose is only an O(log n) factor more than that of their optimal sequential counterparts. We further adapt an algorithm for minimizing sum of linear fractionals, that has inherent parallelism, to solve in parallel the global optimization problems associated with our solution for the weighted region optimal link problem.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parallel optimal weighted links'. Together they form a unique fingerprint.

Cite this