The clustering matroid and the optimal clustering tree
The clustering matroid and the optimal clustering tree
复制标题
DOI：
10.1007/s10107-003-0410-x
复制
发表时间：
2003-09-01
影响因子：
2.7
通讯作者：
Stern, M
中科院分区：
文献类型：
--
作者：
Korach, E;Stern, M
我们考虑以下问题：给定一个完整的图G =（v，e），在每个边缘和V给定的亚集合中都有成本，我们必须找到最低成本跨越树t，以使顶点的每个子集中的每个子集中该集合在T中诱导了一个子树。此问题的一个动机是为非分散客户组的集合构建一个最低成本通信树网络，以便该网络将提供``组可容忍度''和``集体隐私''。我们将此问题建模为矩阵。我们将其扩展到一般的Matroids，并将其称为新的Matroids``聚集Matroids''。我们定义了聚类树问题的三种变体，并表明从算法的角度来看，它们在多项式上是等效的。我们为三种变体之一提供了一种多项式算法，这意味着所有这些算法都可以通过多项式求解。对于集合中子集的基数不超过三个的情况，我们提供了一种贪婪的算法，线性算法以及所有可行解决方案的凸面的多面体描述。
We consider the following problem: Given a complete graph G=(V,E) with a cost on every edge and a given collection of subsets of V, we have to find a minimum cost spanning tree T such that each subset of the vertices in the collection induces a subtree in T. One motivation for this problem is to construct a minimum cost communication tree network for a collection of non-disjoint groups of customers such that the network will provide ``group fault tolerance'' and ``group privacy''. We model this problem as a matroid. We extend it to general matroids and call the new matroids ``clustering matroids''. We define three variations of the clustering tree problem and show that from an algorithmic point of view they are polynomially equivalent. We present a polynomial algorithm for one of the three variations, which implies that all of them can be solved polynomially. For the case where the cardinality of the subsets in the collection does not exceed three, we provide a greedy algorithm, a linear algorithm and also a polyhedron description of the convex hull of all the feasible solutions.