Abstract
The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. In this paper, we investigate in the faulty star graph the ring embedding problem. It has been shown that a ring containing at least n!-4f nodes can be embedded in an n-dimensional star graph or n-star graph with f≤n-3 faulty nodes, where n! is processor number of the n-star graph. In this paper, a long-ring embedding scheme is proposed which can be used to embed a ring with at least n!-2f nodes in an n-star graph to achieve tolerance of up to the same number of faulty nodes. Our results outperform those presented by Y.C. Tseng and colleagues in 1997.The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. In this paper, we investigate in the faulty star graph the ring embedding problem. It has been shown that a ring containing at least n! - 4f nodes can be embedded in an n-dimensional star graph or n-star graph with f≤n - 3 faulty nodes, where n! is processor number of the n-star graph. In this paper, a long-ring embedding scheme is proposed which can be used to embed a ring with at least n! - 2f nodes in an n-star graph to achieve tolerance of up to the same number of faulty nodes. Our results outperform those presented by Y.C. Tseng and colleagues in 1997.