Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
复制标题
DOI：
10.1007/978-3-540-92182-0_20
复制
发表时间：
2008-12
期刊：
影响因子：
1.1
通讯作者：
Takehiro Ito;T. Uno;Xiaoping Zhou;Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Takehiro Ito;T. Uno;Xiaoping Zhou;Takao Nishizeki
设图G的每个顶点都被赋予一个非负的整数权值，并且landu是整数，使得0 ≤l≤u。人们希望通过从G中删除边来将G划分为连通的分量，使得每个分量的总权重至少为t，至多为u。这样的“几乎均匀”划分称为（l，u）-划分。我们处理了三个问题，以找到一个给定的图的（l，u）-分区：最小分区问题是找到一个（l，u）-分区与最小数目的组件;最大分区问题的定义类似;和p-分区问题是找到一个（l，u）-分区与给定数目p的组件。所有这些问题即使对于串-并图也是NP-难的，但对于线性时间的路和多项式时间的树是可解的。本文给出了求解这三个问题的多项式时间算法，它比已知的算法简单得多，速度也快得多。
Assume that each vertex of a graphGis assigned a nonnegative integer weight and thatlanduare integers such that 0 ≤l≤u. One wishes to partitionGinto connected components by deleting edges fromGso that the total weight of each component is at leastland at mostu. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph: the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and thep-partition problem is to find an (l,u)-partition with a given numberpof components. All these problems are NP-hard even for series-parallel graphs, but are solvable for paths in linear time and for trees in polynomial time. In this paper, we give polynomial-time algorithms to solve the three problems for trees, which are much simpler and faster than the known algorithms.