The Transactions of the Korea Information Processing Society (한국정보처리학회논문지)

Korea Information Processing Society (한국정보처리학회)
권호 표지

Cycle Property in the (n,k)-star Graph

(n,k)-스타 그래프의 사이클 특성

  • 장정환 (한국전기통신공사 통신망관리센터)
  • Published : 2000.05.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we analyze the cycle property of the (n,k)-star graph that has an attention as an alternative interconnection network topology in recent years. Based on the graph-theoretic properties in (n,k)-star graphs, we show the pancyclic property of the graph and also present the corresponding algorithm. Based on the recursive structure of the graph, we present such top-down approach that the resulting cycle can be constructed by applying series of "dimension expansion" operations to a kind of cycles consisting of sub-graphs. This processing naturally leads to such property that the resulting cycles tend to be integrated compactly within some minimal subset of sub-graphs, and also means its applicability of another classes of the disjoint-style cycle problems. This result means not only the graph-theoretic contribution of analyzing the pancyclic property in the underlying graph model but also the parallel processing applications such a as message routing or resource allocation and scheduling in the multi-computer system with the corresponding interconnection network.

본 논문에서는 최근 상호연결망 위상으로 관심을 받고 있는 (n,k)-스티 그래프에 대한 사이클 특성을 분석한다.(n,k)-스티 그래프의 그래프 이론적 특성을 바탕으로 (n,k)-스티 그래프가 다양한 종류의 사이클들을 보유하고있는 범사이클(pancyclic)특성을 지니고 있음을 밝히고 해당 사이클들을 찾을 수 있는 알고리즘을 제시한다. 본 논문에서제안하고 있는 기법은 그래프자체의 체귀적 성질을 이용한 하형식(top-down)방식으로써 부-그래프들로 구성된 확장된 개념의 사이클들에 "차원확장"이라는 연산을 연속적으로 적용함으로써 원하는 사이클로 구체화해 가는 과정으로 진행하게 된다. 이러한 기법의 적용 결과 구성되는 사이클은 최소한의 한정된 부-그래프들로 밀집되어 모이는 경향이 있어 노드 또는 예지심에 서로 중복이 없이 독립된(disjoint) 사이클을 찾는 문제 등의 응용분야로 확대적용의 가능성이 있다. 본 연구 결과는 (n,k)-스티 그래프에 대한 그래프 이론적 관점에서의 댐사이클 특성을 분석한 이론적 의미와 더불어 해당 상호연결망 구조를 갖는 다중컴퓨터시스템에서의 메시지 라우팅이나 자원 할당 및 스케쥴링과 관련된 분야로의 응용가능성을 함께 의미하고 있다.

Keywords

References

  1. F. Berman and L. Snyder, 'On mapping parallel algorithms into parallel architectures,' J. of Parallel and Distrib. Comput., Vol.4, pp.439-458, 1987 https://doi.org/10.1016/0743-7315(87)90018-9
  2. B. Monien and H. Sudborough, 'Embedding one interconnection network in another,' Computing Supplement, Vol.7, pp.257-282, 1990
  3. Y. Saad and M. H. Schultz, 'Topological properties of hypercubes,' IEEE Trans. on Comput., Vol.37, pp.867-872, 1988 https://doi.org/10.1109/12.2234
  4. S. B. Akers, D. Harel, and B. Krishnamurthy, 'The star graph: An attractive alternative to the n-cube,' Proc. of the Int'l Conf. on Parallel Processing, pp. 393-400, 1987
  5. K. Day and A. Tripathi, 'A comparative study of topological properties of hypercubes and star graphs,' IEEE Trans. on Paral. and Distrib. Sys., Vol.5, No.1, pp.31-38, 1994 https://doi.org/10.1109/71.262586
  6. W. K. Chiang and R. J. Chen, 'The (n,k)-star graph: A generalized star graph,' Inf. Process. Lett., Vol.56, pp.259-264, 1995
  7. J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall, 'Embedding of cycles and grids in star graphs,' Proc. of the Symp. on Parallel and Distrib. Processing, pp.540-547, 1990 https://doi.org/10.1109/SPDP.1990.143600
  8. M. Nigam, S. Sahni, and B. Krishnamurthy, 'Embedding hamiltonians and hypercubes in star interconnection graphs,' Proc. of the Int'l Conf. on Parallel Processing, pp.340-343, 1990
  9. 박천웅, 장직현 '(n,k)-스타 그래트상의 헤밀토니안임베딩', 한국정보과학회 논문지(A), Vol.25, No.12, pp.1384-1391, 1998
  10. 장정환, 좌경룡, '(n,k)-스타 그래프에서의 새로운 링 임베딩 및 고장허용 임베딩으로의 응용', 한국정보과학회 논문지 : 시스템 및 이론, Vol.27, pp.313-323, 2000
  11. Y. C. Tseng, D. K. Panda, and T. H. Lai, 'A trip- based multicasting model in wormhole-routed networks with virtual channels,' IEEE Trans. on Paral. and Distrib. Sys., Vol.7, No.2, pp.138-150, 1996 https://doi.org/10.1109/71.485503