樹的核與中心的并行算法研究.pdf

1、選址理論是研究在給定的網(wǎng)絡中如何確定滿足特定條件“設施”的最佳位置的組合優(yōu)化理論，在交通運輸、計算機網(wǎng)絡、通信工程等領域有著廣泛而重要的應用. 傳統(tǒng)選址理論中往往把“設施”抽象為點.然而，在許多實際應用中，由于設施所占的空間太大而不能僅僅看作一個點.為了更好的研究這類設施，很多研究者把這種不能看作是單個點的設施抽象成網(wǎng)絡中的路或者是樹狀網(wǎng)絡.目前，關于網(wǎng)絡中路或樹狀網(wǎng)絡設施的最佳位置的衡量標準主要基于最小(大)離心率、最小(大)

2、距離總和等(所謂離心率最小指從“設施”到最遠結點的距離最??；距離總和最小是指從“設施”到所有結點的距離總和最小). 本文主要基于最小離心率、最小距離總和兩個優(yōu)化標準研究如下幾個選址問題：樹狀網(wǎng)絡中含k個葉結點的離心率最小的子樹(即所謂樹的k-樹中心問題)；樹狀網(wǎng)絡中含k個葉結點的距離總和最小的子樹(即所謂樹的k-樹核問題)；含k個葉結點的、直徑至多為l的、離心率最小的子樹(即所謂樹的(k，l)-中心問題)；至多含k個葉結點的、直

3、徑至多為l的、距離總和最小的子樹(即所謂樹的k-樹核問題). 具體成果如下： (1)用EREWPRAM模型構造了一個k-樹中心的并行算法，其算法時間復雜度是用O(n)個處理器，執(zhí)行時間為O(logn)，降低了Wang(Findingak-treecoreandak-treecenterofatreenetworkinparallel.IEEETrans.Par.andDis.Sys.,1998)給出的k-樹中心并行算法.

4、 (2)利用歐拉回路和樹收縮方法，提出了一個有效的k-樹核并行算法，執(zhí)行EREWPRAM模型，算法時間復雜度是用O(n)個處理器，執(zhí)行時間為O(logn).改進了Wang給出的k-樹核并行算法Wang(Findingak-treecoreandak-treecenterofatreenetworkinparallel.IEEETrans.Par.andDis.Sys.,1998)，并降低了時間復雜度. (3)在k-樹中心