N-Star网络中最优的点到多点平行路由算法

Ｃｈｅｎ等研究了ｎ－Ｓｔａｒ网络中的点到多点并行路由问题，对前人的工作做了很大的改进，给出了一个几乎最优的时间复杂度为Ｏ（ｎ２）的算法．由Ｃｈｅｎ的算法所给出的ｎ－１条路Ｐ２，…，Ｐｎ满足｜Ｐｉ｜ｄｉｓｔ（ｖ１，ｖｉ）＋６，其中Ｐｉ是连接ｖｉ到ｖ１的路，｜Ｐｉ｜表示路Ｐｉ的长度，ｄｉｓｔ（ｖ１，ｖｉ）表示ｖｉ到ｖ１的最短路的长度．作者进一步改进了Ｃｈｅｎ等的结果，给出了一个新的时间复杂度仍为Ｏ（ｎ２）的算法，然而该算法给出的内部无交路Ｐ２，…，Ｐｎ满足｜Ｐｉ｜ｄｉｓｔ（ｖ１，ｖｉ）＋４（２ｉｎ），而且无论在时间上还是在生成路的长度上，均是最优的．