延遲差異限制多播樹問題之近似解之複雜度

Abstract

在本篇論文，我們所要研究的主題是如何在多播通訊點對點延遲限制下，和目的節點之間的傳輸延遲差異限制下來建立一個多播樹。也就是說，給定一個電腦網路，一個起始節點是一組多播目的節點，如何找到一個多播樹，它以起始節點為根節點而以多播目的節點為樹葉，使得起始節點到每一個目的節點之點對點延遲在一個可容許的範圍內，並且目的節點之間的延遲差異亦在一個可容許的範圍內。這個問題是首先被[2]所定義和討論，他們稱這個問題為延遲和延遲差異限制多播樹問題。他們證明這是- NP-完全性問題。因此，在本篇論文中，我們將僅討論延遲差異限制多播樹問題。進一步的，我們發現要求得延遲差異限制多播樹問常數倍近似解是一個NP-hard問題。當我們把這個問題從一般網路搬到單一延遲網路(即網路上每一個連結的延遲均為I)來考慮時，我們發現結果是一樣的，也就是說，單一延遲網路之延遲差異限制多播樹問題是 - NP-完全性問題，而它的常數位近似解是一個NP-hard問題。