圓盤圖中最小連通k-全控制集問題的算法

在本論文中，我們提出并研究雙向圓盤圖中的最小連通k全控制集問題，該問題在無線網絡的虛擬骨干網的構造中有著很重要的意義。以前這方面的工作大多數是在單位圓盤中分析，然而，在WSN中，每個傳感器節點的傳輸半徑并一定相同。在本論文中，我們給出了一個集中式近似算法來構造最小連通k全控制集(totally connected k-dominating set)，簡記為k-MTCDS，通過理論分析，我們給出有較好的近似比的近似算法。