排序方式: 共有28条查询结果,搜索用时 21 毫秒
1.
Jheng-Cheng Chen 《Information Sciences》2011,181(3):620-627
The dual-cube is an interconnection network for linking a large number of nodes with a low node degree. It uses low-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube. A dual-cube DC(n) has n + 1 links per node where n is the degree of a cluster (n-cube), and one more link is used for connecting to a node in another cluster. In this paper, assuming each node is incident with at least two fault-free links, we show a dual-cube DC(n) contains a fault-free Hamiltonian cycle, even if it has up to 2n − 3 link faults. The result is optimal with respect to the number of tolerant edge faults. 相似文献
2.
The bubble-sort graph is an important interconnection network designed from Cayley graph model. One conjecture is proposed in Shi and Lu (2008) [10] as follows: for any integer n?2, if n is odd then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles; if n is even then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles and its perfect matching that has no edges in common with the hamiltonian cycles. In this paper, we prove that conjecture is true for n=5,6. 相似文献
3.
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n2logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n2logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n2logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time. 相似文献
4.
The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n − 5 link faults. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its occurrence probability, which is very close to 1. 相似文献
5.
Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m ? 2 and d ? 8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F = {(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs. 相似文献
6.
7.
Louis Ibarra 《Information Processing Letters》2009,109(18):1105-1108
We present an algorithm to find a Hamiltonian cycle in a proper interval graph in O(m+n) time, where m is the number of edges and n is the number of vertices in the graph. The algorithm is simpler and shorter than previous algorithms for the problem. 相似文献
8.
Nicholas Korpelainen Dmitriy S. Malyshev Alexander Tiskin 《Theoretical computer science》2011,412(29):3545-3554
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and vertexk-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any k>3 there is a continuum of boundary classes for vertexk-colorability. 相似文献
9.
Generalized honeycomb torus is a candidate for interconnection network architectures, which includes honeycomb torus, honeycomb rectangular torus, and honeycomb parallelogramic torus as special cases. Existence of Hamiltonian cycle is a basic requirement for interconnection networks since it helps map a “token ring” parallel algorithm onto the associated network in an efficient way. Cho and Hsu [Inform. Process. Lett. 86 (4) (2003) 185-190] speculated that every generalized honeycomb torus is Hamiltonian. In this paper, we have proved this conjecture. 相似文献
10.