Journal
THEORETICAL COMPUTER SCIENCE
Volume 767, Issue -, Pages 1-15Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.09.020
Keywords
Multiprocessor systems; Interconnection networks; Fault tolerance; Prescribed linear forests; Hamiltonian paths
Categories
Funding
- NSFC [U1304601]
- Henan Province [U1304601]
Ask authors/readers for more resources
The k-ary n-cube is an important underlying topology for large-scale multiprocessor systems. A linear forest in a graph is a subgraph each component of which is a path. In this paper, we investigate the problem of embedding hamiltonian paths passing through a prescribed linear forest in ternary n-cubes with faulty edges. Given a faulty edge set F with at most 2n - 3 edges and a linear forest L with at most 2n - 3 - vertical bar F vertical bar edges, for two distinct vertices in the ternary n-cube, we show that the ternary n-cube admits a fault-free hamiltonian path between u and v passing through L if and only if none of the paths in L has u or v as internal vertices or both of them as end-vertices. (C) 2018 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
Recommended
No Data Available