ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES

摘要

We equate a routing algorithm in a (faulty) interconnection network whose underlyingngraph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixednsource node to a fixed destination node, with the sub-digraph of (healthy) links poten-ntially usable by this routing algorithm as it attempts to route the packet. This givesnrise to a naturally defined problem, parameterized by this routing algorithm, relating tonwhether a packet can be routed from a given source node to a given destination nodenin one of our interconnection networks in which there are (possibly exponentially many)nfaulty links. We show that there exist such problems that are PSPACE-complete (allnare solvable in PSPACE) but that there are (existing and popular) routing algorithmsnfor which the computational complexity of the corresponding problem is significantlyneasier (yet still computationally intractable).