帅天平
研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求, 要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束, 使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究, 此时问题是多项式时间可求解的. 其次对树网络
进行了讨论,证明了即使是星网络,问题也不存在近似比小于$m^{\frac{1}{2}-\rho}(0<\rho<1))$的近似算法,除非$NP=ZPP$,这里~$m$~是星图的边数.随后给出了近似比为
$(\sqrt{m}+1)\big(\log{\frac{r}{\sqrt{m}+1}}+1\big)$
的近似算法,此结果对一般图也成立.最后考虑了环网和树环网, 给出了近似比为~3.6 和 $2\Delta$ 的近似算法, 这里$\Delta$是图的最大度.