论文部分内容阅读
这篇论文主要考虑给定一个原点和一组终点,如何找到一个多播多分光路路由和多播多分光-树路由使得该路由的费用最小而且需要的波长数目最少,该文首先证明了求最小费用的多播多分光-树路由在一些特殊情况下是多项式时间内可解的而对于一般情况是NP-完全的;然后给出具有近似比小于4的有效的多播多分光路路由的近似算法和近似比小于5的多播多分光-树路由的近似算法.所做的模拟表明相对点到点的路由,多分路由不但可以显著地节省网络费用,而且还可以大大地节省波长的数目.更进一步,它的费用是在一点到多点路由（基于Steiner树的）模型所用的费用的一个很小的常数倍以内.