A NOVEL ROUTING SCHEME ON THE STAR AND PANCAKE NETWORKS AND ITS APPLICATIONS

A new scheme for routing data on the star and pancake networks is described. It unifies data routing on these two networks, and makes them as powerful as the hypercube when solving a host of problems. Consequently, it allows a certain class of algorithms designed for the hypercube to be implemented directly on the star and pancake networks without time loss. The new scheme is used to derive parallel (star and pancake) algorithms for computing minimum spanning forests in both sparse and dense weighted graphs. The time complexities of these algorithms match those of the equivalent hypercube algorithms. These results take added importance when one recalls the many attractive properties that the star and pancake networks possess by comparison with the hypercube, in particular their smaller degree and diameter.