본문 바로가기
KERD
논문KCI 등재

An Embedding of Multiple Edge-Disjoint Hamiltonian Cycles on Enhanced Pyramid Graphs

장정환
한국정보처리학회|2011.03|JIPS(Journal of Information Processing Systems) (Journal of Information Processing Systems)|제7권 제1호|pp. 75-84

1

조회

0

다운로드

0

인용

0

참고문헌

키워드

Hamiltonian CycleEnhanced Pyramid ModelEdge-Disjoint Cycle

초록

The enhanced pyramid graph was recently proposed as an interconnection network model in parallel processing for maximizing regularity in pyramid networks. We prove that there are two edge-disjoint Hamiltonian cycles in the enhanced pyramid networks. This investigation demonstrates its superior property in edge fault tolerance. This result is optimal in the sense that the minimum degree of the graph is only four.

Abstract

The enhanced pyramid graph was recently proposed as an interconnection network model in parallel processing for maximizing regularity in pyramid networks. We prove that there are two edge-disjoint Hamiltonian cycles in the enhanced pyramid networks. This investigation demonstrates its superior property in edge fault tolerance. This result is optimal in the sense that the minimum degree of the graph is only four.

참고문헌 (20)

  1. F. Berman, "On mapping parallel algorithms into parallel architectures", Jr. of Parellel and Distrib. Comput, 4(1), pp.439~458 (1987)
  2. S. G. Akl, "Parallel Computation: Models and Methods" (1997), Prentice Hall
  3. B. Monien, "Embedding one interconnection network in another", Computing Supplement, 7(1), pp.257~282 (1990)
  4. R. Miller, "Data movement techniques for the pyramid computer", SIAM J. on. Comput, 16(1), pp.38~60 (1987)
  5. F. T. Leighton, "Introduction to parallel algorithms and architectures: arrays, trees, hypercubes" (1991), Morgan Kaufmann
  6. Q. F. Stout, "Mapping vision algorithms to parallel architectures", Proc. of the IEEE, 7(1), pp.982~995 (1988)
  7. L. Cinque, "Parallel prefix computation on a pyramid computer", Patt. Recog. Lett, 16(1), pp.19~22 (1995)
  8. J. F. Jenq, "Image shrinking and expanding on a pyramid", IEEE Trans. Parallel Distrib. Syst, 4(11), pp.1291~1296 (1993)
  9. R. Cipher, "SIMD architectures and algorithms for image processing and computer vision", IEEE Trans. Acoust. Speech Signal Process, 37(12), pp.2158~2174 (1989)
  10. R. Miller, "Data movement techniques for the pyramid compute", SIAM J. Comput, 16(1), pp.38~60 (1987)
  11. H. Sarbazi-Azad, "Algorithmic construction of Hamiltonians in pyramids", Inform. Process. Lett, 80(2), pp.75~79 (2001)
  12. D. –R. Dui, "Proof that pyramid networks are 1-Hamiltonian-connected with high probability", Information Sciences, 177(24), pp.4188~4199 (2007)
  13. R. –Y. Wu, "Hamiltonicity of the pyramid network with or without fault", Journal of Information Science and Engineering, 25, pp.531~542 (2009)
  14. F. Cao, "Fault tolerance properties of pyramid networks", IEEE Trans. Comput, 48(1), pp.88~93 (1999)
  15. J. S. -T. Juan, "On the strong distance problems of pyramid networks", Applied Mathematics and Computation, 195, pp.154~161 (2008)
  16. K. W. Tang, "Diagonal and toroidal mesh networks", IEEE Trans. Comput, 43(7), pp.815~826 (1994)
  17. Y. -C. Chen, "On the enhanced pyramid network", Proc. 2004 International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, pp.1483~1489 (2004)
  18. Y. -C. Chen, "Proof that enhanced pyramid networks are 2-edge-Hamiltonicity", Proc. The 23rd Workshop on Combinatorial Mathematics and Computation Theory, Las Vegas, Nevada, pp.76~84 (2006)
  19. Y. -C. Chen, "An optimal broadcasting algorithm for the enhanced pyramid network", Proc. The 22nd Workshop on Combinatorial Mathematics and Computation Theory, National Cheng Kung University, Taiwan, pp.206~211 (2005)
  20. A. Caruso, "Fault-diagnosis of grid structures", Theoretical Computer Science, 290(2), pp.1149~1174 (2003)

관련 논문AI추천

Circulant Decompositions of Certain Multipartite Graphs into Gregarious Cycles of a Given Length조정래영남수학회 · East Asian Mathematical Journal2014 · 제30권 제3호Edge-Maximal θ2k+1-Edge Disjoint Free GraphsMohammed M. M. Jaradat, Mohammed S. A. Bataineh경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2014 · 제54권 제1호DISJOINT CYCLES WITH PRESCRIBED LENGTHS AND INDEPENDENT EDGES IN GRAPHSHong Wang대한수학회 · 대한수학회지2014 · 제51권 제5호Sufficient condition for the existence of three disjoint theta graphsDing Ma, Yunshu Gao대한수학회 · 대한수학회보2015 · 제52권 제1호ON DECOMPOSITIONS OF THE COMPLETE EQUIPARTITE GRAPHS Kkm(2t) INTO GREGARIOUS m-CYCLES김성근영남수학회 · East Asian Mathematical Journal2013 · 제29권 제3호메쉬에 두 개의 링크를 추가한 연결망의 에지 고장 해밀톤 성질박경욱, 임형석한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2004 · 제11권 제3호

이 간행물의 다른 논문 (18건)

Computer Simulation: A Hybrid Model for Traffic Signal OptimisationMohamed Kamal JBIRA, Munir AHMEDpp. 1-16A Single Mobile Target Tracking in Voronoi-based Clustered Wireless Sensor NetworkMitsuji Matsumoto, Jiehui Chen, Mariam B.Salimpp. 17-28A Clustering Protocol with Mode Selection for Wireless Sensor NetworkAries Kusdaryono, 이경오pp. 29-42Analytical Coexistence Benchmark for Assessing the Utmost Interference Tolerated by IEEE 802.20Mouhamed Abdulla, Yousef R. Shayanpp. 43-52Dynamic Load Balancing and Network Adaptive Virtual Storage Service for Mobile AppliancesIvy Ong, 임효택pp. 53-62
원문 보기