On the computational complexity of routing in faulty k-ary n-cubes and hypercubes.

Stewart, I.A.

Abstract

We equate a routing algorithm in a (faulty) interconnection network whose underlying graph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixed source node to a fixed destination node, with the sub-digraph of (healthy) links potentially usable by this routing algorithm as it attempts to route the packet. This gives rise to a naturally defined problem, parameterized by this routing algorithm, relating to whether a packet can be routed from a given source node to a given destination node in one of our interconnection networks in which there are (possibly exponentially many) faulty links. We show that there exist such problems that are PSPACE-complete (all are solvable in PSPACE) but that there are (existing and popular) routing algorithms for which the computational complexity of the corresponding problem is significantly easier (yet still computationally intractable).

Citation

Stewart, I. (2012). On the computational complexity of routing in faulty k-ary n-cubes and hypercubes. Parallel Processing Letters, 22(1), Article 1250003. https://doi.org/10.1142/s012962641250003x

• Journal Article Type: Article
• Publication Date: 2012-03
• Deposit Date: Aug 25, 2011
• Journal: Parallel Processing Letters
• Print ISSN: 0129-6264
• Electronic ISSN: 1793-642X
• Publisher: World Scientific Publishing
• Peer Reviewed: Peer Reviewed
• Volume: 22
• Issue: 1
• Article Number: 1250003
• DOI: https://doi.org/10.1142/s012962641250003x