论文部分内容阅读
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）的多项式时间算法。