본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

메쉬 연결망의 강한 해밀톤 laceability
Strongly Hamiltonian Laceability of Mesh Networks

박경욱   (전남대학교 전산학과UU0001112  ); 임형석   (전남대학교 전산학과UU0001112  );
  • 초록

    상호 연결망에서 해밀톤 경로는 선형 배열 구현이나 멀티캐스팅과 같은 여러 응용에서 활용된다. 본 논문에서는 여러 병렬 시스템의 상호연결망으로 사용되는 메쉬 연결망의 해밀톤 성질에 대해 고려한다. 연결망이 강한 해밀톤 laceable이면 그 연결망은 임의의 두 노드를 잇는 가능한 가장 긴 길이의 경로를 지닌다. 2차원 메쉬 M(m, n)은 노드의 수가 짝수이면 $m{\geq}4,\;n{\geq}4$ 일 때, 노드의 수가 홀수이면 $m{\geq}3,\;n{\geq}3$ 일 때 강한 해밀톤 laceable 그래프임을 보인다. 메쉬는 토러스, k-ary n-큐브, 하이퍼큐브, 재귀원형군과 같은 여러 상호 연결망들의 스패닝 부 그래프이므로 본 논문의 결과는 이들 연결망들의 고장 해밀톤 성질을 밝히는데 활용될 수 있다.


    In interconnection networks, a Hamiltonian path has been utilized in many applications such as the implementation of linear array and multicasting. In this paper, we consider the Hamiltonian properties of mesh networks which are used as the topology of parallel machines. If a network is strongly Hamiltonian laceable, the network has the longest path joining arbitrary two nodes. We show that a two-dimensional mesh M(m, n) is strongly Hamiltonian laceabie, if $m{\geq}4,\;n{\geq}4(m{\geq}3,\;n{\geq}3\;respectively)$ , and the number of nodes is even(odd respectively). A mesh is a spanning subgraph of many interconnection networks such as tori, hypercubes, k-ary n-cubes, and recursive circulants. Thus, our result can be applied to discover the fault-hamiltonicity of such networks.


  • 주제어

    메쉬 .   해밀톤 경로 .   강한 해밀톤 laceable 그래프.  

  • 참고문헌 (13)

    1. Intel Corporation literature, Intel Corporation, 1991 
    2. C.-H. Tsai, J. M. Tan, T. Lian, and L.-H. Hsu, 'Fault-tolerant hamiltonian laceability of hypercubes,' Information Processing Letters, Vol. 83, pp. 301-306, 2002 
    3. C.-H. Tsai, J. M. Tan, Y. C. Chuang, and L.-H. Hsu, 'Fault-free cycles and links in faulty recursive circulant graphs,' Proc. of the ICS 2000 Workshop on Algorithms and Theory of Computation, pp, 74-77, 2000 
    4. Y. A. Ashir and I. A. Stewart, 'Fault-tolerant embeddings of hamiltonian circuits in k-ary n-cubes,' SIAM Journal on Discrete mathematics, Vol. 15, No. 3, pp. 317-328, 2002 
    5. W. T. Huang, Y. C. Chuang, J. J. Tan, and L. H. Hsu, 'On the fault-tolerant hamiltonicity of faulty crossed cubes,' IEICE Trans. Fundamentals, Vol. E85-A, No. 6, pp. 1359-1370, 2002 
    6. G. Simmons, 'Almost all n-dimensional rectangular lattices are Hamilton laceable,' Congressus Numerantium, Vol. 21, 649-661, 1978 
    7. S. Y. Hsieh, G. H. Chen, and C. W. Ho, 'Hamiltonian-laceability of star graphs,' Networks, Vol. 36, No. 4, pp. 225-232, 2000 
    8. J. H. Park and H. C. Kim, 'Fault hamiltonicity of product graph of path and cycle,' International Conference, Computing and Combinatorics Conference (COCOON), pp. 319-328, 2003 
    9. C. C. Chen and N. F. Quimpo, 'On strongly hamiltonian abelian group graphs,' Combinatorial Mathematics VIII. Lecture Notes in Mathematics, Vol. 884, pp. 23-34, 1980 
    10. S. D. Chen, H. Shen, and R. W. Topor, 'An efficient algorithm for constructing hamiltonian paths in meshes,' Parallel Computing, Vol. 28, pp. 1293-1305, 2002 
    11. A. Itai, C. H. Papadimitriou, and J. L. Czwarcfiter, 'Hamiltonian paths in grid graphs,' SIAM Journal on Computing, Vol. 11, No. 4, pp. 676-686, 1982 
    12. J. S. Kim, S. R. Maeng, and H. Yoon, 'Embedding of rings in 2-D meshes and tori with faulty nodes,' Journal of Systems Architecture, Vol. 43, pp. 643-654, 1997 
    13. S. D. Chen, H. Shen, and R. W. Topor, 'Permutation-based range-join algorithms on N-dimensional meshes,' IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 4, pp. 413-431, 2002 

 저자의 다른 논문

  • 박경욱 (11)

    1. 2003 "두 개의 랩어라운드 에지를 갖는 메쉬의 고장 해밀톤 성질" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (7): 434~444    
    2. 2004 "메쉬에 두 개의 링크를 추가한 연결망의 에지 고장 해밀톤 성질" 정보처리학회논문지. The KIPS transactions. Part A. Part A a11 (3): 189~198    
    3. 2011 "무선 센서 네트워크에서 에너지 효율적인 트래픽 제어 메커니즘" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 15 (10): 2257~2264    
    4. 2011 "웹기반의 온실환경 원격 모니터링 시스템 구축" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 6 (1): 77~83    
    5. 2011 "스마트 폰 기반 홈 자동제어시스템 설계 및 구현" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 6 (4): 589~594    
    6. 2013 "야외 증강현실 기반의 문화 유적지 3D 모델 시각화 시스템" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 8 (3): 459~464    
    7. 2014 "크레인 디스크 패드 모니터링을 위한 스마트폰 기반의 열영상 진단 시스템 개발" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 9 (12): 1397~1404    
    8. 2015 "그린에너지 자립섬을 위한 계통 독립형 마이크로그리드 모니터링 시스템 설계 및 구현" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 10 (4): 527~532    
    9. 2015 "시설하우스 온도 조절을 위한 수직형 교반 히터 자동제어 시스템" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 10 (5): 623~628    
    10. 2006 "실시간 특수효과를 위한 라이브러리 및 생성기 개발" 한국콘텐츠학회 2006년도 춘계 종합학술대회 논문집 2006 (5): 499~502    
  • 임형석 (18)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기