메쉬에 두 개의 링크를 추가한 연결망의 에지 고장 해밀톤 성질
Edge Fault Hamiltonian Properties of Mesh Networks with Two Additional Links
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 메쉬 연결망의 첫 행과 마지막 행에 랩어라운드 링크를 갖는 연결망의 고장 해밀톤 성질을 고려한다. 이분 그래프인에 하나의 결함 링크가 발생했을 때 임의의 두 노드가 다른(같은) 집합에 속한 경우 두 노드를 잇는 길이 인 경로가 존재함을 보인다. [1]에서 보인의 연구 결과와 비교하면 또한 이러한 해밀톤 성질을 지닌다. 그러나이 개의 랩어라운드 에지를 지니는 것에 반해은 단지 두 개의 링크를 추가하여 이러한 해밀톤 성질을 지닌다. 또한 은 다차원 메쉬, 재귀원형군, 하이퍼큐브, 이중 루프 네트워크,-ary -큐브와 같은 여러 상호 연결망의 스패닝 부 그래프이다. 따라서 의 고장 해밀톤 성질은 이들 연결망들의 고장 해밀톤 성질을 밝히는데 활용될 수 있다. 본 논문의 결과를 3차원 메쉬, 재귀원형군, 하이퍼큐브에 적용시켜 이들 연결망의 고장 해밀톤 성질들을 보인다.
Abstract
We consider the fault hamiltonian properties of meshes with two wraparound links on the first row and the last row, denoted by ,,., which is bipartite, with a single faulty link has a fault-free path of length between arbitrary two nodes if they both belong to the different(same) partite set. Compared with the previous works of[1], it also has these hamiltonian properties. Our result show that two additional wraparound links are sufficient for an mesh to have such properties rather than wraparound links. Also, is a spanning subgraph of many interconnection networks such as multidimensional meshes, recursive circulants, hypercubes, double loop networks, and-ary-cubes. Thus, our results can be applied to discover fault-hamiltonicity of such interconnection networks. By applying hamiltonian properties of to 3-dimensional meshes, recursive circulants, and hypercubes, we obtain fault hamiltonian properties of these networks.
참고문헌 (23)
- "Fault hamiltonicity of product graph of path and cycle", pp.319~328 (2003)
- "'Introduction to Parallel Algorithms and Architectures：Arrays" (1992), Cailf.：Morgan-Kaufmann
- "On the fault tolerance of some popular bounded-degree networks", pp.542~552 (1992)
- "A fault tolerant massively parallel processing architecture", 4, pp.363~383 (1987)
- "Proc. IEEE Symp. Foundations of Computer Science", pp.693~702 (1992)
- "Fault tolerant meshes with small degree", 26(6), pp.1764~1784 (1997)
- "Fault tolerant meshes with small degree", 51(5), pp.553~560 (2002)
- "Fault tolerant hamiltonian laceability of hypercubes", (83), pp.301~306 (2002)
- "Fault free cycles and links in faulty recursive circulant graphs", pp.74~77 (2000)
- "Fault tolerant embeddings of hamiltonian circuits in k ary n cubes", 15(3), pp.317~328 (2002)
- "On the fault tolerant hamiltonicity of faulty crossed cubes", E85-A(6), pp.1359~1370 (2002)
- "Almost all n-dimensional rectangular lattices are Hamiltonian laceable", 21, pp.103~108 (1978)
- "Hamiltonian laceability of star graphs", 36(4), pp.225~232 (2000)
- "On strongly hamiltonian abelian group graphs", 884, pp.23~34 (1980)
- "An efficient algorithm for constructing hamiltonian paths in meshes", 28, pp.1293~1305 (2002)
- "Hamiltonian paths in grid graphs", 11(4), pp.676~686 (1982)
- "Permutation based range join algorithms on N dimensional meshes", 13(4), pp.413~431 (2002)
- "Embedding of rings in 2 D meshes and tori with faulty nodes", 43, pp.643~654 (1997)
- H. C. Kim, "Fault hamiltonicity of two dimensional torus networks", pp.110~117 (2000)
- 박경욱, "두 개의 랩어라운드 에지를 갖는 메쉬의 고장 해밀톤 성질", 30(8), pp.434~444 (2003)
- C. -H. Tsai, "Hamiltonian properties of faulty recursive circulant graphs", 3(3&4), pp.273~289 (2002)
- S. Latifi, "Optimal ring embedding in hypercubes with faulty links Proc. International Symposium on Fault-Tolerant Computing", pp.178~184 (1992)
- S. Latifi, "Hamiltonian path and cycle in hypercubes with faulty links", pp.471~478 (2002)