On the Computational Complexity of Routing in Faulty k-ary n-Cubes and Hypercubes
On the Computational Complexity of Routing in Faulty k-ary n-Cubes and Hypercubes
复制标题
DOI：
10.1142/s012962641250003x
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
I. A. Stewart
中科院分区：
文献类型：
--
作者：
I. A. Stewart
我们等同于（故障）互连网络的路由算法，其底层图是一个k元n-立方体或超立方体，试图从一个固定的源节点到一个固定的目的地节点的数据包路由，与（健康）链路的子有向图潜在可用的路由算法，因为它试图路由数据包。这就产生了一个自然定义的问题，参数化的路由算法，涉及到一个数据包是否可以从一个给定的源节点路由到一个给定的目的地节点，在我们的互连网络中，有（可能是指数很多）错误的链接。我们发现，存在这样的问题，是PSPACE完整的（都是可解决的PSPACE），但有（现有的和流行的）路由算法，相应的问题的计算复杂性是显着容易（但仍然计算棘手）。
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).