K. Qiu and S.G. Akl (Canada)
interconnection network, star graph, routing algorithm, dis joint paths.
We study the problem of finding disjoint paths between two nodes in a star interconnection network. Specifically, we show a simple routing algorithm that finds n − 1 disjoint paths between any two nodes s and t in an n-star in optimal O(n2 ) time such that no path has length more than d(s, t) + 4, where d(s, t) is the shortest path length between s and t. This result matches those obtained earlier. However, our approach is different from the early ones, and the disjoint ness of parallel paths is proven easily by noting that these paths are in different sub-stars. In addition, it also reveals certain interesting properties of star graphs.
Important Links:
Go Back
