论文部分内容阅读
Spider graph问题是组合最优化方面的典型优化问题,在光纤网络传输方面也涉及到该问题。T=(V,E)为一棵树,在T中至多有一个结点的度大于2,则称T为Spidergraph。我们所研究的问题是:给定一棵树T=(V,E),寻找E的子集E(即E'∈E),使得在树T中去除E’后剩余图(即T-E’)的每个连通分支为spidergraph,其目标是使去除边的数目/E'/达到最小,即min/E'/。本论文给出了该问题的一个复杂性为O(n)的多项式时间算法。