加權樹的分割

Abstract

在許多實際的應用上，我們常常需要把一個加權榭分割成最多的子樹，同時又必須要求每個子樹的權數在一定的大小之上。本文中，我們針對不同的加權方式，設計出一些有效率的演算法。

In models of many real applications, we very often need to partition a tree into as many subtrees as possible and keep the weight of every subtree larger than a given constant. In this thesis, we design efficient algorithms for the above tree partition problem under different weight requirements.