樹(shù)的核與中心的并行算法研究.pdf

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

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

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

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