Analysis of the Minimum and Maximum Numbers of Edges per Each Dimension Required for Constructing a Hamiltonian Cycles in the Star Graph Interconnection Networks
Junghwan Chang · The Journal of Korean Institute of Information Technology · 2016
스타 그래프는 기반 토폴로지로서의 매력적인 특성들을 보유하고 있기 때문에 대규모 병렬컴퓨팅 응용에서 사용되는 상호연결망 토폴로지로 잘 알려진 모델이다. 본 논문에서는 n!개의 노드와 (n-1)n!/2개의 간선을 갖는 n-차원 스타 그래프 상호연결망에서 해밀톤 사이클 구성 시 필요한 각 차원별 간선 수의 최소값 및 최대 값을 분석한다. 해밀톤 사이클 구성 시 어떤 차원에서는 최대에 해당하는 5n!/12개의 간선이 필요함을 보인다. 아울러 어떤 차원에서는 최소에 해당하는 n 개의 간선만 있으면 충분하다. 이러한 연구 결과는 고장-허용 사이클 임베딩 문제에서 허용가능한 고장 원소의 개수의 관점에서 허용가능한 최대 및 최소 한계값과 관련이 있는 연구분야에서 기초로 사용될 수 있을 것으로 기대된다.