Computational complexity of long paths and cycles in faulty hypercubes
Computational complexity of long paths and cycles in faulty hypercubes
复制标题
DOI：
10.1016/j.tcs.2010.07.001
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Tomáš Dvořák;V. Koubek
中科院分区：
文献类型：
--
作者：
Tomáš Dvořák;V. Koubek
在具有 f 个故障顶点的 n 维超立方体中存在最佳长度（长）无故障环的问题是 NP 困难的。即使 f 受关于 n 的三（六）次多项式限制，这也成立。另一方面，f 存在线性（二次）界限，这保证了问题在多项式时间内可判定。对于路径以及规定端点之间的路径可以获得类似的结果。
The problem of existence of an optimal-length (long) fault-free cycle in the n-dimensional hypercube with f faulty vertices is NP-hard. This holds even in case that f is bounded by a polynomial of degree three (six) with respect to n. On the other hand, there is a linear (quadratic) bound on f which guarantees that the problem is decidable in polynomial time. Similar results are obtained for paths as well as for paths between prescribed endvertices.