Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Iain Stewart

Stewart, I.A. & Xiang, Y. (2009). Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems 20(1): 25-33.

Author(s) from Durham

Abstract

In this paper we give precise solutions to problems posed by Wang, An, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Q_n^k is bipanconnected and edge-bipancyclic, when k ≥ 3 and n ≥ 2, and we also show that when k is odd, Q_n^k is m-panconnected, for m = (n(k-1)+2k-6)\2, and (k-1)-pancyclic (these bounds are optimal). We introduce a path-shortening technique, called progressive shortening, and strengthen existing results, showing that when paths are formed using progressive shortening then these paths can be efficiently constructed and used to solve a problem relating to the distributed simulation of linear arrays and cycles in a parallel machine whose interconnection network is Q_n^k, even in the presence of a faulty processor.