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

IAIN A. STEWART

首页> 外文期刊>Parallel Processing Letters >ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES

【24h】

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

机译：故障K-ary N立方和超立方的布线计算复杂度

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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).

机译：我们将（故障）互连网络中的路由算法等同于其基础图是k元n多维数据集或超多维数据集，该路由算法尝试将数据包从fixedn源节点路由到固定目标节点，并以（健康）链接，此路由算法在尝试路由数据包时可能会使用该链接。这引起了一个自然定义的问题，该问题由该路由算法进行了参数化，涉及到是否可以在我们的互连网络之一（可能存在指数级错误连接）中将数据包从给定的源节点路由到给定的目标节点。我们表明存在这样的问题，它们是PSPACE完全的（在PSPACE中可解决所有问题），但存在（现有和流行的）路由算法，对于这些算法，相应问题的计算复杂度明显较差（但在计算上仍然难以解决）。

著录项

来源
《Parallel Processing Letters》 |2012年第1期|p.1-13|共13页
作者
IAIN A. STEWART;
展开▼
作者单位

School of Engineering and Computing Sciences, Durham UniversityScience Labs, South Road, Durham DH1 3LE, U.K.;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
routing; computational complexity; k-ary n-cubes; hypercubes;

机译：路由;计算复杂度;k进制n多维数据集;超立方体;

相似文献

外文文献
中文文献
专利

1. ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES [J] . IAIN A. STEWART Parallel Processing Letters . 2012,第1期

机译：故障K-ary N立方和超立方的路由计算复杂度
2. DISTRIBUTED ALGORITHMS FOR BUILDING HAMILTONIAN CYCLES IN k-ARY n-CUBES AND HYPERCUBES WITH FAULTY LINKS [J] . IAIN A. STEWART Journal of interconnection networks . 2007,第3期

机译：在具有故障链接的k元n立方和超立方中建立哈密顿循环的分布式算法
3. Unpaired Many-to-Many Disjoint Path Covers on Bipartite k-Ary n-Cube Networks with Faulty Elements [J] . International Journal of Foundations of Computer Science . 2020,第3期

机译：在具有故障元素的二分钟K-ARY N-CUBE网络上取消了许多多对多的不相交路径覆盖
4. Distributed Algorithms for Building Hamiltonian Cycles in k-ary n-cubes and Hypercubes with Faulty Links [C] . Stewart, I.A. . 2006

机译：在具有错误链接的k元n立方体和超立方体中构建哈密顿循环的分布式算法
5. Design and implementation of the Java-based hybrid interconnection network simulator (JABHINS) and its application to clustered k-ary n-cube networks. [D] . Cestero Rivera, Alberto. 2001

机译：基于Java的混合互连网络模拟器（JABHINS）的设计和实现及其在群集k元n立方网络中的应用。
6. Parallel computation for biological sequence comparison: comparing a portable model to the native model for the Intel Hypercube. [O] . P. M. Nadkarni, P. L. Miller 1991

机译：用于生物学序列比较的并行计算：将便携式模型与Intel Hypercube的本机模型进行比较。
7. Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links. [O] . Stewart I. A. 2007

机译：用于在具有错误链接的k元n立方和超立方中构建哈密顿循环的分布式算法。

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

摘要

著录项

相似文献

相关主题

期刊订阅