Fault-tolerant ring embedding in a star graph with both link and node failures
Citations Over TimeTop 10% of 1997 papers
Abstract
The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. Previously, the star graph has been shown to contain a Hamiltonian cycle. In this paper, we consider an injured star graph with some faulty links and nodes. We show that even with f/sub e//spl les/n-3 faulty links, a Hamiltonian cycle still can be found in an n-star, and that with f/sub v//spl les/n-3 faulty nodes, a ring containing at most 4f/sub v/ nodes less than that in a Hamiltonian cycle can be found (i.e. the ring contains at least n!-4f/sub v/ nodes). In general, in an n-star with f/sub e/ faulty links and f/sub v/ faulty nodes, where f/sub e/+f/sub v//spl les/n-3, our embedding is able to establish a ring containing at least n!-4f/sub v/ nodes.