Balanced Partition of Minimum Spanning Trees
Balanced Partition of Minimum Spanning Trees
复制标题
DOI：
10.1142/s0218195903001190
复制
发表时间：
2002-04
期刊：
影响因子：
--
通讯作者：
Mattias Andersson;Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
中科院分区：
文献类型：
--
作者：
Mattias Andersson;Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
为了更好地处理有额外资源可用于执行任务的情况，制造业中的许多问题都涉及“最佳”地将任务划分为 k 个较小的任务。我们考虑将给定的 n 个点集 S（在平面上）划分为 k 个子集 S1,...,Sk 的问题，使得 max1?i?k|MST(Si)|被最小化。这个问题的一个变体出现在造船业中[2]。
To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve "optimally" dividing a task into k smaller tasks. We consider the problem of partitioning a given set S of n points (in the plane) into k subsets, S1,...,Sk, such that max1?i?k|MST(Si)| is minimized. A variant of this problem arises in the shipbuilding industry [2].