Jung Hwan Chang

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 7, No. 5, pp. 1464-1473, May. 2000
10.3745/KIPSTE.2000.7.5.1464,   PDF Download:

Abstract

In this paper, we analyze the cycle property of the (n,k)-star graph that has an attention as an alternative interconnection network topology in recent years. Based on the graph-theoretic properties in (n,k)-star graphs, we show the pancyclic property of the graphs and also present the corresponding algorithm. Based on the recursive structure of the graph, we present such top-down approach that the resulting cycle can be constructed by applying series of "dimension expansion" operations to a kind of cycles consisting of sub-graphs. This processing naturally leads to such property that the resulting cycles tend to be integrated compactly within some minimal subset of sub-graphs, and also means its applicability to another classes of the disjoint-style cycle problems. This result means not only the graph-theoretic contribution of analyzing the pancyclic property in the underlying graph model but also the parallel processing applications such as message routing or resource allocation and scheduling in the multi-computer system with the corresponding interconnection network.

Statistics
Cite this article