叢集生成樹之演算法問題;On the clustered spanning tree problem

[[abstract]]在很多網路拓樸的應用中，終端機常會因為安全或效率的關係而分成很多群，因此在同一群的終端機可以在群內選擇路徑。在這個情況下，我們希望找到一顆生成樹，使得群內的每一個點都叢集在一起。在這篇論文中，我們研究兩個叢集生成樹問題，它們的點都分成數群，第一個是最小路由叢集生成樹問題，另一個是最小史坦納叢集生成樹問題。在本論文的第一個部分，我們研究最小路由叢集生成樹問題。給定一個點分成k 群的輸入圖，我們定義一個叢集生成樹的子樹彼此都不相交。我們在最小路由叢集生成樹這個問題證明了不可近似的結果。在輸入圖為metric graph時，我們提出了一個兩倍的近似演算法。我們也研究它的延伸問題，當目標為找不同群間的路徑時，我們證明了在輸入圖分成兩群時可以多項式函數時間求得解，當分成三群時則是NP-hard。當分成三群時我們提出了一個兩倍的近似演算法。在本論文的第二個部分，我們研究當輸入圖為metric graph 的最小史坦納叢集生成樹問題，它是最小史坦納樹的延伸問題。我們證明了在叢集生成樹的條件下，給定了群與群之間的拓樸和群內的拓樸後，這個問題仍然是NP-hard。我們證明了叢集生成樹的史塔納樹ratio 是介於三到四之間。我們也提出了一個(ρ+2)倍的近似演算法，ρ是當前最好的史塔納樹近似演算法。當給定了群內的拓樸後，可以找到(ρ+1)倍的近似演算法。我們也研究了其他的延伸問題，一個是只找群與群之間的史坦納叢集生成樹，另一個是在已知群與群之間的最小史塔納叢集生成樹，找群內的最小史塔納叢集生成樹。 In many network applications, terminals may be grouped into clusterssuch that the communications between terminals of the same cluster shouldbe routed \locally" for the sake of efficiency and safety. In such case, welook for a spanning tree in which vertices of each cluster should be clusteredtogether. In this thesis, we study two different kinds of clustered spanningtree problem where the set of vertices is partitioned into clusters: one is the minimum routing cost clustered tree problem, the other one is the clustered Steiner tree problem.In the rst part of this thesis, we investigate the minimum routing costclustered tree problem. For an edge-weighted graph G = (V,E,w), in whichthe vertices are partitioned into k clusters, a spanningtree is a clustered spanning tree if the subtrees spanning the clusters are mutually disjoint. We show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a metric graph. We also study a variant in whichthe objective function is the total distance summed over all pairs of verticesof different clusters. We show that the problem is polynomial-time solvablewhen the number of clusters k is 2 and NP-hard for k = 3. We propose apolynomial-time 2-approximation algorithm for the case of 3 clusters.In the second part of this thesis, we study the Clustered Steiner tree prob-lem on metric graphs, which is a variant of Steiner minimum tree problem. Inthis problem, the required vertices are partitioned into clusters, and the sub-trees spanning different clusters must be disjoint in a feasible clustered Steiner tree. We show that the problem is NP-hard even if the local-topologies and the inter-cluster tree are given. We show that the Steiner ratio of this problem is lower and upper bounded by three and four, respectively. We also propose a (ρ+2)-approximation algorithm, where is the approximation ratio for the Steiner minimum tree problem, and the approximation ratio can be improvedto ρ+ 1 if the local topologies are given. Two variants of this problem arealso studied. When the goal is to minimize the inter-cluster cost and ignorethe cost of local trees, the problem can be solved in polynomial time. But itis NP-hard if we ask for the minimum cost of local trees among all solutionswith minimum inter-cluster cost