Partitioning trees of supply and demand
Partitioning trees of supply and demand
复制标题
DOI：
10.1142/s0129054105003303
复制
发表时间：
2002-11
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;Xiaoping Zhou;Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Xiaoping Zhou;Takao Nishizeki
假设一棵树T有ns个“供应顶点”，所有其他顶点都是“需求顶点”。“每个供应顶点被分配一个称为供应的正数，而每个需求顶点被分配一个称为需求的正数。人们希望通过删除T中的边将T划分为恰好ns个子树，使得每个子树恰好包含一个供应顶点，其供应不小于子树中所有需求顶点的需求之和。“划分问题”是一个判定问题，询问T是否有这样的划分。“最大划分问题”是划分问题的优化版本。在本文中，我们给出了三个算法的问题。第一个是线性时间算法的划分问题。第二个是最大划分问题的伪多项式时间算法。第三是一个完全多项式时间近似计划（FPTAS）的最大分割问题。
Assume that a tree T has a number ns of "supply vertices" and all the other vertices are "demand vertices." Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wish to partition T into exactly ns subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.