Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor
Embedding long paths in k-ary n-cubes with faulty nodes and links
Stewart, I.A.; Xiang, Y.
Authors
Y. Xiang
Abstract
Let $k \geq 4$ be even and let $n \geq 2$. Consider a faulty k-ary n-cube $Q_n^k$ in which the number of node faults $f_n$ and the number of link faults $f_e$ are such that $f_n + f_e \leq 2n-2$. We prove that given any two healthy nodes s and e of $Q_n^k$, there is a path from s to e of length at least $k^n - 2f_n - 1$ (resp. $k^n - 2f_n - 2$) if the nodes s and e have different (resp. the same) parities (the parity of a node in $Q_n^k$ is the sum modulo 2 of the elements in the n-tuple over {0, 1, ..., k-1} representing the node). Our result is optimal in the sense that there are pairs of nodes and fault configurations for which these bounds cannot be improved, and it answers questions recently posed by Yang, Tan and Hsu, and by Fu. Furthermore, we extend known results, obtained by Kim and Park, for the case when n = 2.
Citation
Stewart, I., & Xiang, Y. (2008). Embedding long paths in k-ary n-cubes with faulty nodes and links. IEEE Transactions on Parallel and Distributed Systems, 19(8), 1071-1085. https://doi.org/10.1109/tpds.2007.70787
Journal Article Type | Article |
---|---|
Publication Date | Aug 1, 2008 |
Deposit Date | Jun 29, 2009 |
Publicly Available Date | Mar 28, 2024 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Print ISSN | 1045-9219 |
Publisher | Institute of Electrical and Electronics Engineers |
Peer Reviewed | Peer Reviewed |
Volume | 19 |
Issue | 8 |
Pages | 1071-1085 |
DOI | https://doi.org/10.1109/tpds.2007.70787 |
Publisher URL | http://www.dur.ac.uk/i.a.stewart/Papers/embedding.pdf |
Files
Published Journal Article
(1.3 Mb)
PDF
You might also like
One-to-many node-disjoint paths in (n,k)-star graphs
(2010)
Journal Article
Pancyclicity and panconnectivity in augmented k-ary n-cubes
(2009)
Conference Proceeding
Pancyclicity in faulty k-ary 2-cubes
(2009)
Conference Proceeding
Bipanconnectivity and bipancyclicity in k-ary n-cubes
(2009)
Journal Article
Using semidirect products of groups to build classes of interconnection networks
(2020)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search