에지 고장이 있는 Restricted Hypercube-Like 그래프의 해밀톤 경로
Hamiltonian Paths in Restricted Hypercube-Like Graphs with Edge Faults
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Restricted Hypercube-Like(RHL) 그래프는 교차큐브, 뫼비우스큐브, 엠큐브, 꼬인큐브, 지역꼬인큐브, 다중꼬인큐브, 일반꼬인큐브와 같이 유용한 상호연결망들을 광범위하게 포함하는 그래프군이다. 본 논문에서는 m≥4 인 m-차원 RHL 그래프 G에 대해서 임의의 에지 집합 F⊂E(G), ∣F∣≤m-2, 가 고장일 때, 고장 에지들을 제거한 그래프 G∖F는 임의의 서로 다른 두 정점 s와 t에 대해서 dist(s, V(F))≠1 이거나dist(t, V(F))≠1이면 해밀톤 경로가 있음을 보인다. V(F)는 F에 속하는 에지들의 양 끝점들의 집합이고 dist(v, V(F))는 정점 v와 집합 V(F)의정점들 간의 최소 거리이다.
Abstract
Restricted Hypercube-Like (RHL) graphs are a graph class that widely includes useful interconnection networks such as crossed cube,Möbius cube, Mcube, twisted cube, locally twisted cube, multiply twisted cube, and generalized twisted cube. In this paper, we show that for an m-dimensional RHL graph G, m≥4, with an arbitrary faulty edge set F⊂E(G), ∣F∣≤m-2, graph G∖F has a hamiltonian path between any distinct two nodes s and t if dist(s, V(F))≠1 or dist(t, V(F))≠1. Graph G∖F is the graph G whose faulty edges are removed. Set V(F) is the end vertex set of the edges in F and dist(v, V(F)) is the minimum distance between vertex v and the vertices in V(F).
참고문헌 (17)
- J.-H. Park, "Fault-hamiltonicity of hypercube-like interconnection networks", Proc. of IEEE International Parallel & Distributed Processing Symposium IPDPS2005 (2005)
- A. S. Vaidya, "A class of hypercube-like networks", Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing SPDP 1993, pp.800~803 (1993)
- K. Efe, "The crossed cube architecture for parallel computation", IEEE Trans. on Parallel and Distributed Systems, 3(5), pp.513~524 (1992)
- P. Cull, "The Möbius cubes", IEEE Transactions on Computers, 44(5), pp.647~659 (1995)
- N. K. Singhvi, "The Mcube: a symmetrical cube based network with twisted links", Proc. of the 9th IEEE Int. Parallel Processing Symposium IPPS 1995, pp.11~16 (1995)
- P. A. J. Hilbers, "The Twisted Cube, In PARLE: Parallel Architectures and Languages Europe, Vol. I: Parallel Architectures", pp.152~159 (1987), Springer
- X. Yang, "The locally twisted cubes", International Journal of Computer Mathematics, 82(4), pp.401~413 (2005)
- K. Efe, "A variation on the hypercube with lower diameter", IEEE Trans. on Computers, 40(11), pp.1312~1316 (1991)
- F. B. Chedid, "A new variation on hypercubes with smaller diameter", Information Processing Letters, 46(6), pp.275~280 (1993)
- J.-H. Park, "Recursive circulants and their embeddings among hypercubes", Theoretical Computer Science, 244(1-2), pp.35~62, Elsevier BV
- X. Yang, "Hamiltonian properties of twisted hypercube-like networks with more faulty elements", Theoretical Computer Science, 412(22), pp.2409~2417 (2011)
- S. Wang, "Embedding hamiltonian paths in k -ary n-cubes with conditional edge faults", Theoretical Computer Science, 412(46), pp.6570~6584 (2011)
- T. Kueng, "Long paths in hypercubes with conditional node-faults", Information Sciences, 179(5), pp.667~681 (2009)
- J.-H. Park, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements", THEORETICAL COMPUTER SCIENCE, 377(1-3), pp.170~180, ELSEVIER SCIENCE BV
- S. Y. Hsieh, "Pancyclicity of restricted hypercube-like networks under the conditional fault model", SIAM Journal on Discrete Mathematics, 23(4), pp.2100~2119 (2010)
- N. Biggs, "Algebraic Graph Theory, 2rid ed" (1993), Cambridge Univ. Press
- J.-H. Park, "Many-to-many disjoint path covers in the presence of faulty elements", IEEE Trans. Computers, 58(4), pp.528~540 (2009)