TY - JOUR
T1 - Parallel optimal weighted links
AU - Daescu, Ovidiu
AU - Cheung, Yam K.
AU - Palmer, James D.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=67650434470&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67650434470&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00212-0_4
DO - 10.1007/978-3-642-00212-0_4
M3 - Conference article
AN - SCOPUS:67650434470
SN - 0302-9743
VL - 5300 LNCS
SP - 66
EP - 81
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -