樹分割問題

On the Tree Partition Problems

李至軒(Chih-Hsuan Li)

指導教授 ： 王炳豐

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

https://doi.org/10.6843/NTHU.2013.00672

摘要

考慮一 n 個 vertices 的 tree T，每個 vertex 上都有一個非負整數的 weight，而每一條 edge 上都有一個正整數的 cost。一個 T 的 partition 為在 T 上刪除一些 edges 後所形成的 subtrees。令 l 和 u 為兩個非負整數且 l <= u。一個 [l, u]-partition 為一每個 subtree 的 weight 都在 [l, u] 中的 partition。一個 p-[l, u]-partition 為一有 p 個 subtrees 的 [l, u]-partition。一個 partition 的 cost 定義為被刪除的 edge 的 cost 總和。本論為的重點為下列兩個問題： (1) 如何求出一個 p-[l, u]-partition 以及 (2) 如何求出一個 minimum-cost [l, u]-partition。對於問題 (1)，本論文提出一 O(n p^{4} loglog p / log^{2} p) 時間的演算法。對於問題 (2)，本論文證明它為 NP-hard 並提出一 O(n u^{2} loglog u / log^{2} u) 時間的 pseudo-polynomial 演算法。上述兩個演算法藉由套用目前最好的 (min, +)-convolution 演算法來加速原本的演算法，分別改進了之前 O(n p^{4}) 及 O(n u^{2}) 的結果。本論文也研究問題 (1) 及問題 (2) 的延伸問題： 如何求出一個 minimum-cost p-[l, u]-partition。對於這個延伸問題，本論文提出一 O(n u^{2} p^{2} loglog p / log^{2} p) 時間的演算法。

關鍵字

演算法 ； 樹形圖 ； 分割問題

並列摘要

Consider a tree T with n vertices, in which each vertex is associated with a nonnegative integer weight and each edge is associated with a positive integer cost. A partition of T is a set of subtrees induced by removing some edges. Let l <= u be two nonnegative integers. An [l, u]-partition is a partition such that the total weight of each subtree is in [l, u]. A p-[l, u]-partition is an [l, u]-partition with p subtrees. The cost of a partition is the total cost of the removed edges. The focus of this thesis is the following two problems: (1) the problem of finding a p-[l, u]-partition and (2) the problem of finding a minimum-cost [l, u]-partition. For (1), an O(n p^{4} loglog p / log^{2} p)-time algorithm is presented. For (2), its NP-hardness is proved. In addition, an O(n u^{2} loglog u / log^{2} u)-time pseudo-polynomial algorithm is presented. The presented algorithms for (1) and (2) improve, respectively, the previous upper bounds from O(n p^{4}) and O(n u^{2}). The improvement is achieved by an efficient application of the current best algorithm for computing the (min, +)-convolution of two vectors to reduce the running time of the previous algorithms. This thesis also considers the following nature extension of (1) and (2): finding a minimum-cost p-[l, u]-partition. For this extended problem, an O(n u^{2} p^{2} loglog p / log^{2} p)-time algorithm is presented.

並列關鍵字

algorithms ； trees ； partition problems

參考文獻

[7] D. Bremner, T. M. Chan, E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, P. Taslakian, ''Necklaces, Convolutions, and X + Y,'' in Proceedings of the 14th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 4168, pp. 160-171, 2006.

[2] R. I. Becker, S. R. Schach, and Y. Perl, "A shifting algorithm for min-max tree partitioning," Journal of the ACM, vol. 29, no. 1, pp. 58-67, 1982.

[3] R. Becker, B. Simeone, and Y-I. Chiang, "A shifting algorithm for continuous tree partitioning," Theoretical Computer Science, vol. 282, no. 2, pp. 353-380, 2002.

[5] B. Bozkaya, E. Erkut, G. Laporte, ''A tabu search heuristic and adaptive memory procedure for political districting,'' European Journal of Operational Research, vol. 144, no. 1, pp. 12–26, 2003.

[8] T.M. Chan, ''More algorithms for all-pairs shortest paths in weighted graphs,'' SIAM Journal on Computing, vol. 39, no. 5, pp. 2075-2089, 2010.