Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 66-81 |
| Number of pages | 16 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 5300 LNCS |
| DOIs | |
| State | Published - 2009 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)