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

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

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