4.3 Article

Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links

Journal

THEORETICAL COMPUTER SCIENCE
Volume 939, Issue -, Pages 161-169

Publisher

ELSEVIER
DOI: 10.1016/j.tcs.2022.10.021

Keywords

Multiprocessor system; Interconnection network; Balanced hypercube; Fault tolerance; Hamiltonian laceability

Ask authors/readers for more resources

This article introduces the n-dimensional balanced hypercube BHn as a candidate interconnection network for multiprocessor systems, and proves that under certain conditions, BHn can achieve fault-free Hamiltonian paths between nodes.
The n-dimensional balanced hypercube BHn is one of candidate interconnection networks for multiprocessor systems, and it is a bipartite graph. Let F be a set of faulty links and L be a fault-free linear forest in BHn. For any two nodes u and v in different parts of BHn such that none of the paths in L has u or v as internal node or both of them as end nodes, we prove that BHn admits a fault-free hamiltonian path between u and v passing through L even if the total number of links in F and L is up to 2n - 2. The upper bound on the number of links in F and L is optimal. This generalizes some known results.(c) 2022 Elsevier B.V. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.3
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available