k-瓶頸斯坦納樹快速近似算法.pdf

1、經(jīng)典斯坦納樹問(wèn)題在超大規(guī)模集成電路設(shè)計(jì)、計(jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)、IC芯片路由、無(wú)線通訊網(wǎng)絡(luò)規(guī)劃以及重建生命演化樹等多個(gè)領(lǐng)域都有非常重要的應(yīng)用，近年來(lái)各個(gè)領(lǐng)域中新的應(yīng)用需要對(duì)經(jīng)典斯坦納樹問(wèn)題進(jìn)行適當(dāng)修改使之更具應(yīng)用價(jià)值，因此對(duì)經(jīng)典斯坦納樹變種問(wèn)題的研究亦具有重要的意義。
　　目前，對(duì)經(jīng)典斯坦納樹變種問(wèn)題的研究主要表現(xiàn)在兩方面，1)：k-瓶頸斯坦納樹問(wèn)題；2)：最大邊長(zhǎng)度限定、尋找包含斯坦納點(diǎn)數(shù)目最少的斯坦納樹問(wèn)題。
　　本文主要是對(duì)網(wǎng)

2、格空間和歐幾里得平面的k-瓶頸斯坦納樹問(wèn)題進(jìn)行研究，具體內(nèi)容如下：
　?。?）從斯坦納樹問(wèn)題的基本理論著手，詳細(xì)說(shuō)明斯坦納樹問(wèn)題的定義，斯坦納樹算法的實(shí)際應(yīng)用，斯坦納樹的變種問(wèn)題。給出L. Wang和D-Z.Du的近似性能比為2的多項(xiàng)式時(shí)間近似算法，并詳細(xì)分析該近似算法的時(shí)間復(fù)雜度。
　?。?）對(duì)L.Wang和D-Z.Du算法的時(shí)間復(fù)雜度進(jìn)行改進(jìn)。提出近似性能比為2的k-瓶頸斯坦納樹算法的優(yōu)化方案，分別使用最大堆和斐波那契堆