论文部分内容阅读
Ｃｈｅｎ等研究了ｎ－Ｓｔａｒ网络中的点到多点并行路由问题，对前人的工作做了很大的改进，给出了一个几乎最优的时间复杂度为Ｏ（ｎ２）的算法．由Ｃｈｅｎ的算法所给出的ｎ－１条路Ｐ２，…，Ｐｎ满足｜Ｐｉ｜ｄｉｓｔ（ｖ１，ｖｉ）＋６，其中Ｐｉ是连接ｖｉ到ｖ１的路，｜Ｐｉ｜表示路Ｐｉ的长度，ｄｉｓｔ（ｖ１，ｖｉ）表示ｖｉ到ｖ１的最短路的长度．作者进一步改进了Ｃｈｅｎ等的结果，给出了一个新的时间复杂度仍为Ｏ（ｎ２）的算法，然而该算法给出的内部无交路Ｐ２，…，Ｐｎ满足｜Ｐｉ｜ｄｉｓｔ（ｖ１，ｖｉ）＋４（２ｉｎ），而且无论在时间上还是在生成路的长度上，均是最优的．
Chen et al. Studied the problem of point-to-multipoint parallel routing in n-Star networks and greatly improved the previous work. An almost optimal algorithm with time complexity of O (n2) is given. The n-1 paths P2, ..., Pn given by Chen’s algorithm satisfy | Pi | dist (v1, vi) +6, where Pi is the path connecting vi to v1, | Pi | dist (v1, vi) represents the length of the shortest path from vi to v1. The author further improves the result of Chen et al. And gives a new algorithm of time complexity O (n2). However, the internal non-intersecting P2, ..., Pn given by the algorithm satisfies | Pi | dist (v1 , Vi) +4 (2in), and is optimal both in time and length of generated path.