Publication details for Professor Iain StewartStewart, I.A. (2012). On the computational complexity of routing in faulty k-ary n-cubes and hypercubes. Parallel Processing Letters 22(1): 1250003
- Publication type: Journal Article
- ISSN/ISBN: 0129-6264, 1793-642X
- DOI: 10.1142/S012962641250003X
- Further publication details on publisher web site
Author(s) from Durham
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).