Authors

null Shyh-Chain Chern, null Tai-Ching Tuan, null Jung-Sing Jwo

Abstract

We show that the two uni-directional n-cubes, namely UHC1/sub n/ and UHC2/sub n/ proposed by Chou and Du (1990) as interconnection schemes are Hamiltonian. In addition, we show that (1) if n is even, both architectures are vertex symmetric; and (2) if n is odd, both architectures have exactly two vertex-symmetric components. By studying symmetry, we further prove that the maximum delay of one-port one-to-all broadcasting for either architecture is at most 1.5n.«ETX»

Citation

  • Journal: Proceedings the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis
  • Year: 2002
  • Volume:
  • Issue:
  • Pages: 183–189
  • Publisher: IEEE Comput. Soc. Press
  • DOI: 10.1109/aispas.1995.401339

BibTeX

@inproceedings{Shyh_Chain_Chern,
  series={AISPAS-95},
  title={{Hamiltonicity, vertex symmetry, and broadcasting of uni-directional hypercubes}},
  DOI={10.1109/aispas.1995.401339},
  booktitle={{Proceedings the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis}},
  publisher={IEEE Comput. Soc. Press},
  author={Shyh-Chain Chern and Tai-Ching Tuan and Jung-Sing Jwo},
  pages={183--189},
  collection={AISPAS-95}
}

Download the bib file

References

  • Lakshmivarahan, S., Jwo, J.-S. & Dhall, S. K. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey. Parallel Computing 19, 361–407 (1993) – 10.1016/0167-8191(93)90054-o
  • Lin, M., Tsang, R., Du, D. H. C., Klietz, A. E. & Saroff, S. Performance evaluation of the CM-5 interconnection network. Digest of Papers. Compcon Spring 189–198 doi:10.1109/cmpcon.1993.289662 – 10.1109/cmpcon.1993.289662
  • Maxemchuk, N. Routing in the Manhattan Street Network. IEEE Trans. Commun. 35, 503–512 (1987) – 10.1109/tcom.1987.1096802
  • Maxemchuk, N. Routing in the Manhattan Street Network. IEEE Trans. Commun. 35, 503–512 (1987) – 10.1109/tcom.1987.1096802
  • schnepf, Blueprint for an Interactive Multimedia Presentation System (1993)
  • leighton, Introduction to Parallel Algorithms and Architectures Arrays Trees Hypercubes (1992)
  • Tan, S. T. & Du, D. H. C. Embedded unidirectional incomplete hypercubes for optical networks. IEEE Trans. Commun. 41, 1284–1289 (1993) – 10.1109/26.237844
  • Vetter, R. J. & Du, D. H. C. Distributed computing with high-speed optical networks. Computer 26, 8–18 (1993) – 10.1109/2.191977
  • Chou, C.-H. & Du, D. H. C. Uni-directional hypercubes. Proceedings SUPERCOMPUTING ’90 254–263 doi:10.1109/superc.1990.130028 – 10.1109/superc.1990.130028
  • (0)
  • Faber, V., Moore, J. W. & Chen, W. Y. C. Cycle prefix digraphs for symmetric interconnection networks. Networks 23, 641–649 (1993) – 10.1002/net.3230230707
  • Day, K. & Tripathi, A. Unidirectional star graphs. Information Processing Letters 45, 123–129 (1993) – 10.1016/0020-0190(93)90013-y
  • Hamidoune, Y. O., Llado, A. S. & Serra, O. The connectivity of hierarchical Cayley digraphs. Discrete Applied Mathematics 37–38, 275–280 (1992) – 10.1016/0166-218x(92)90138-z
  • Gerla, M. Tree-Net, a multi-level fiber optics MAN. IEEE INFOCOM ’88,Seventh Annual Joint Conference of the IEEE Computer and Communcations Societies. Networks: Evolution or Revolution? 363–372 doi:10.1109/infcom.1988.12938 – 10.1109/infcom.1988.12938
  • borgonovo, HR4-NET: A Hierarchical Random-Routing Reliable and Reconfigurable Network for Metropolitan Area. Proc IEEE InfoCom (1987)
  • Akers, S. B. & Krishnamurthy, B. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38, 555–566 (1989) – 10.1109/12.21148
  • lakshmivarahan, Analysis and design of parallel algorithms (1990)